MySQL 5.6.14 Source Code Document
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
mi_packrec.c
1 /* Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.
2 
3  This program is free software; you can redistribute it and/or modify
4  it under the terms of the GNU General Public License as published by
5  the Free Software Foundation; version 2 of the License.
6 
7  This program is distributed in the hope that it will be useful,
8  but WITHOUT ANY WARRANTY; without even the implied warranty of
9  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  GNU General Public License for more details.
11 
12  You should have received a copy of the GNU General Public License
13  along with this program; if not, write to the Free Software
14  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
15 
16  /* Functions to compressed records */
17 
18 #include "fulltext.h"
19 
20 #define IS_CHAR ((uint) 32768) /* Bit if char (not offset) in tree */
21 
22 /* Some definitions to keep in sync with myisampack.c */
23 #define HEAD_LENGTH 32 /* Length of fixed header */
24 
25 #if INT_MAX > 32767
26 #define BITS_SAVED 32
27 #define MAX_QUICK_TABLE_BITS 9 /* Because we may shift in 24 bits */
28 #else
29 #define BITS_SAVED 16
30 #define MAX_QUICK_TABLE_BITS 6
31 #endif
32 
33 #define get_bit(BU) ((BU)->bits ? \
34  (BU)->current_byte & ((mi_bit_type) 1 << --(BU)->bits) :\
35  (fill_buffer(BU), (BU)->bits= BITS_SAVED-1,\
36  (BU)->current_byte & ((mi_bit_type) 1 << (BITS_SAVED-1))))
37 #define skip_to_next_byte(BU) ((BU)->bits&=~7)
38 #define get_bits(BU,count) (((BU)->bits >= count) ? (((BU)->current_byte >> ((BU)->bits-=count)) & mask[count]) : fill_and_get_bits(BU,count))
39 
40 #define decode_bytes_test_bit(bit) \
41  if (low_byte & (1 << (7-bit))) \
42  pos++; \
43  if (*pos & IS_CHAR) \
44  { bits-=(bit+1); break; } \
45  pos+= *pos
46 
47 /* Size in uint16 of a Huffman tree for byte compression of 256 byte values. */
48 #define OFFSET_TABLE_SIZE 512
49 
50 static uint read_huff_table(MI_BIT_BUFF *bit_buff,MI_DECODE_TREE *decode_tree,
51  uint16 **decode_table,uchar **intervall_buff,
52  uint16 *tmp_buff);
53 static void make_quick_table(uint16 *to_table,uint16 *decode_table,
54  uint *next_free,uint value,uint bits,
55  uint max_bits);
56 static void fill_quick_table(uint16 *table,uint bits, uint max_bits,
57  uint value);
58 static uint copy_decode_table(uint16 *to_pos,uint offset,
59  uint16 *decode_table);
60 static uint find_longest_bitstream(uint16 *table, uint16 *end);
61 static void (*get_unpack_function(MI_COLUMNDEF *rec))(MI_COLUMNDEF *field,
62  MI_BIT_BUFF *buff,
63  uchar *to,
64  uchar *end);
65 static void uf_zerofill_skip_zero(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
66  uchar *to,uchar *end);
67 static void uf_skip_zero(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
68  uchar *to,uchar *end);
69 static void uf_space_normal(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
70  uchar *to,uchar *end);
71 static void uf_space_endspace_selected(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
72  uchar *to, uchar *end);
73 static void uf_endspace_selected(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
74  uchar *to,uchar *end);
75 static void uf_space_endspace(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
76  uchar *to,uchar *end);
77 static void uf_endspace(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
78  uchar *to,uchar *end);
79 static void uf_space_prespace_selected(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
80  uchar *to, uchar *end);
81 static void uf_prespace_selected(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
82  uchar *to,uchar *end);
83 static void uf_space_prespace(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
84  uchar *to,uchar *end);
85 static void uf_prespace(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
86  uchar *to,uchar *end);
87 static void uf_zerofill_normal(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
88  uchar *to,uchar *end);
89 static void uf_constant(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
90  uchar *to,uchar *end);
91 static void uf_intervall(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
92  uchar *to,uchar *end);
93 static void uf_zero(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
94  uchar *to,uchar *end);
95 static void uf_blob(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
96  uchar *to, uchar *end);
97 static void uf_varchar1(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
98  uchar *to, uchar *end);
99 static void uf_varchar2(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
100  uchar *to, uchar *end);
101 static void decode_bytes(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
102  uchar *to,uchar *end);
103 static uint decode_pos(MI_BIT_BUFF *bit_buff,MI_DECODE_TREE *decode_tree);
104 static void init_bit_buffer(MI_BIT_BUFF *bit_buff,uchar *buffer,uint length);
105 static uint fill_and_get_bits(MI_BIT_BUFF *bit_buff,uint count);
106 static void fill_buffer(MI_BIT_BUFF *bit_buff);
107 static uint max_bit(uint value);
108 #ifdef HAVE_MMAP
109 static uchar *_mi_mempack_get_block_info(MI_INFO *myisam, MI_BIT_BUFF *bit_buff,
110  MI_BLOCK_INFO *info, uchar **rec_buff_p,
111  uchar *header);
112 #endif
113 
114 static mi_bit_type mask[]=
115 {
116  0x00000000,
117  0x00000001, 0x00000003, 0x00000007, 0x0000000f,
118  0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff,
119  0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff,
120  0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff,
121 #if BITS_SAVED > 16
122  0x0001ffff, 0x0003ffff, 0x0007ffff, 0x000fffff,
123  0x001fffff, 0x003fffff, 0x007fffff, 0x00ffffff,
124  0x01ffffff, 0x03ffffff, 0x07ffffff, 0x0fffffff,
125  0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff,
126 #endif
127  };
128 
129 
130  /* Read all packed info, allocate memory and fix field structs */
131 
132 my_bool _mi_read_pack_info(MI_INFO *info, pbool fix_keys)
133 {
134  File file;
135  int diff_length;
136  uint i,trees,huff_tree_bits,rec_reflength,length;
137  uint16 *decode_table,*tmp_buff;
138  ulong elements,intervall_length;
139  uchar *disk_cache;
140  uchar *intervall_buff;
141  uchar header[HEAD_LENGTH];
142  MYISAM_SHARE *share=info->s;
143  MI_BIT_BUFF bit_buff;
144  DBUG_ENTER("_mi_read_pack_info");
145 
146  if (myisam_quick_table_bits < 4)
147  myisam_quick_table_bits=4;
148  else if (myisam_quick_table_bits > MAX_QUICK_TABLE_BITS)
149  myisam_quick_table_bits=MAX_QUICK_TABLE_BITS;
150 
151  file=info->dfile;
152  my_errno=0;
153  if (mysql_file_read(file, (uchar*) header, sizeof(header), MYF(MY_NABP)))
154  {
155  if (!my_errno)
156  my_errno=HA_ERR_END_OF_FILE;
157  goto err0;
158  }
159  /* Only the first three bytes of magic number are independent of version. */
160  if (memcmp((uchar*) header, (uchar*) myisam_pack_file_magic, 3))
161  {
162  my_errno=HA_ERR_WRONG_IN_RECORD;
163  goto err0;
164  }
165  share->pack.version= header[3]; /* fourth byte of magic number */
166  share->pack.header_length= uint4korr(header+4);
167  share->min_pack_length=(uint) uint4korr(header+8);
168  share->max_pack_length=(uint) uint4korr(header+12);
169  elements=uint4korr(header+16);
170  intervall_length=uint4korr(header+20);
171  trees=uint2korr(header+24);
172  share->pack.ref_length=header[26];
173  rec_reflength=header[27];
174  diff_length=(int) rec_reflength - (int) share->base.rec_reflength;
175  if (fix_keys)
176  share->rec_reflength=rec_reflength;
177  share->base.min_block_length=share->min_pack_length+1;
178  if (share->min_pack_length > 254)
179  share->base.min_block_length+=2;
180  DBUG_PRINT("info", ("fixed header length: %u", HEAD_LENGTH));
181  DBUG_PRINT("info", ("total header length: %lu", share->pack.header_length));
182  DBUG_PRINT("info", ("pack file version: %u", share->pack.version));
183  DBUG_PRINT("info", ("min pack length: %lu", share->min_pack_length));
184  DBUG_PRINT("info", ("max pack length: %lu", share->max_pack_length));
185  DBUG_PRINT("info", ("elements of all trees: %lu", elements));
186  DBUG_PRINT("info", ("distinct values bytes: %lu", intervall_length));
187  DBUG_PRINT("info", ("number of code trees: %u", trees));
188  DBUG_PRINT("info", ("bytes for record lgt: %u", share->pack.ref_length));
189  DBUG_PRINT("info", ("record pointer length: %u", rec_reflength));
190 
191  /*
192  Memory segment #1:
193  - Decode tree heads
194  - Distinct column values
195  */
196  if (!(share->decode_trees=(MI_DECODE_TREE*)
197  my_malloc((uint) (trees*sizeof(MI_DECODE_TREE)+
198  intervall_length*sizeof(uchar)),
199  MYF(MY_WME))))
200  goto err0;
201  intervall_buff=(uchar*) (share->decode_trees+trees);
202 
203  /*
204  Memory segment #2:
205  - Decode tables
206  - Quick decode tables
207  - Temporary decode table
208  - Compressed data file header cache
209  This segment will be reallocated after construction of the tables.
210  */
211  length=(uint) (elements*2+trees*(1 << myisam_quick_table_bits));
212  /*
213  To keep some algorithms simpler, we accept that they access
214  bytes beyond the end of the input data. This can affect up to
215  one byte less than the "word size" size used in this file,
216  which is BITS_SAVED / 8. To avoid accessing non-allocated
217  data, we add (BITS_SAVED / 8) - 1 bytes to the buffer size.
218  */
219  if (!(share->decode_tables=(uint16*)
220  my_malloc((length + OFFSET_TABLE_SIZE) * sizeof(uint16) +
221  (uint) (share->pack.header_length - sizeof(header) +
222  (BITS_SAVED / 8) - 1), MYF(MY_WME | MY_ZEROFILL))))
223  goto err1;
224  tmp_buff=share->decode_tables+length;
225  disk_cache= (uchar*) (tmp_buff+OFFSET_TABLE_SIZE);
226 
227  if (mysql_file_read(file, disk_cache,
228  (uint) (share->pack.header_length-sizeof(header)),
229  MYF(MY_NABP)))
230  goto err2;
231 
232  huff_tree_bits=max_bit(trees ? trees-1 : 0);
233  init_bit_buffer(&bit_buff, disk_cache,
234  (uint) (share->pack.header_length-sizeof(header)));
235  /* Read new info for each field */
236  for (i=0 ; i < share->base.fields ; i++)
237  {
238  share->rec[i].base_type=(enum en_fieldtype) get_bits(&bit_buff,5);
239  share->rec[i].pack_type=(uint) get_bits(&bit_buff,6);
240  share->rec[i].space_length_bits=get_bits(&bit_buff,5);
241  share->rec[i].huff_tree=share->decode_trees+(uint) get_bits(&bit_buff,
242  huff_tree_bits);
243  share->rec[i].unpack=get_unpack_function(share->rec+i);
244  DBUG_PRINT("info", ("col: %2u type: %2u pack: %u slbits: %2u",
245  i, share->rec[i].base_type, share->rec[i].pack_type,
246  share->rec[i].space_length_bits));
247  }
248  skip_to_next_byte(&bit_buff);
249  /*
250  Construct the decoding tables from the file header. Keep track of
251  the used memory.
252  */
253  decode_table=share->decode_tables;
254  for (i=0 ; i < trees ; i++)
255  if (read_huff_table(&bit_buff,share->decode_trees+i,&decode_table,
256  &intervall_buff,tmp_buff))
257  goto err3;
258  /* Reallocate the decoding tables to the used size. */
259  decode_table=(uint16*)
260  my_realloc((uchar*) share->decode_tables,
261  (uint) ((uchar*) decode_table - (uchar*) share->decode_tables),
262  MYF(MY_HOLD_ON_ERROR));
263  /* Fix the table addresses in the tree heads. */
264  {
265  my_ptrdiff_t diff=PTR_BYTE_DIFF(decode_table,share->decode_tables);
266  share->decode_tables=decode_table;
267  for (i=0 ; i < trees ; i++)
268  share->decode_trees[i].table=ADD_TO_PTR(share->decode_trees[i].table,
269  diff, uint16*);
270  }
271 
272  /* Fix record-ref-length for keys */
273  if (fix_keys)
274  {
275  for (i=0 ; i < share->base.keys ; i++)
276  {
277  MI_KEYDEF *keyinfo= &share->keyinfo[i];
278  keyinfo->keylength+= (uint16) diff_length;
279  keyinfo->minlength+= (uint16) diff_length;
280  keyinfo->maxlength+= (uint16) diff_length;
281  keyinfo->seg[keyinfo->flag & HA_FULLTEXT ?
282  FT_SEGS : keyinfo->keysegs].length= (uint16) rec_reflength;
283  }
284  if (share->ft2_keyinfo.seg)
285  {
286  MI_KEYDEF *ft2_keyinfo= &share->ft2_keyinfo;
287  ft2_keyinfo->keylength+= (uint16) diff_length;
288  ft2_keyinfo->minlength+= (uint16) diff_length;
289  ft2_keyinfo->maxlength+= (uint16) diff_length;
290  }
291  }
292 
293  if (bit_buff.error || bit_buff.pos < bit_buff.end)
294  goto err3;
295 
296  DBUG_RETURN(0);
297 
298 err3:
299  my_errno=HA_ERR_WRONG_IN_RECORD;
300 err2:
301  my_free(share->decode_tables);
302 err1:
303  my_free(share->decode_trees);
304 err0:
305  DBUG_RETURN(1);
306 }
307 
308 
309 /*
310  Read a huff-code-table from datafile.
311 
312  SYNOPSIS
313  read_huff_table()
314  bit_buff Bit buffer pointing at start of the
315  decoding table in the file header cache.
316  decode_tree Pointer to the decode tree head.
317  decode_table IN/OUT Address of a pointer to the next free space.
318  intervall_buff IN/OUT Address of a pointer to the next unused values.
319  tmp_buff Buffer for temporary extraction of a full
320  decoding table as read from bit_buff.
321 
322  RETURN
323  0 OK.
324  1 Error.
325 */
326 
327 static uint read_huff_table(MI_BIT_BUFF *bit_buff, MI_DECODE_TREE *decode_tree,
328  uint16 **decode_table, uchar **intervall_buff,
329  uint16 *tmp_buff)
330 {
331  uint min_chr,elements,char_bits,offset_bits,size,intervall_length,table_bits,
332  next_free_offset;
333  uint16 *ptr,*end;
334  DBUG_ENTER("read_huff_table");
335 
336  if (!get_bits(bit_buff,1))
337  {
338  /* Byte value compression. */
339  min_chr=get_bits(bit_buff,8);
340  elements=get_bits(bit_buff,9);
341  char_bits=get_bits(bit_buff,5);
342  offset_bits=get_bits(bit_buff,5);
343  intervall_length=0;
344  ptr=tmp_buff;
345  DBUG_PRINT("info", ("byte value compression"));
346  DBUG_PRINT("info", ("minimum byte value: %u", min_chr));
347  DBUG_PRINT("info", ("number of tree nodes: %u", elements));
348  DBUG_PRINT("info", ("bits for values: %u", char_bits));
349  DBUG_PRINT("info", ("bits for tree offsets: %u", offset_bits));
350  if (elements > 256)
351  {
352  DBUG_PRINT("error", ("ERROR: illegal number of tree elements: %u",
353  elements));
354  DBUG_RETURN(1);
355  }
356  }
357  else
358  {
359  /* Distinct column value compression. */
360  min_chr=0;
361  elements=get_bits(bit_buff,15);
362  intervall_length=get_bits(bit_buff,16);
363  char_bits=get_bits(bit_buff,5);
364  offset_bits=get_bits(bit_buff,5);
365  decode_tree->quick_table_bits=0;
366  ptr= *decode_table;
367  DBUG_PRINT("info", ("distinct column value compression"));
368  DBUG_PRINT("info", ("number of tree nodes: %u", elements));
369  DBUG_PRINT("info", ("value buffer length: %u", intervall_length));
370  DBUG_PRINT("info", ("bits for value index: %u", char_bits));
371  DBUG_PRINT("info", ("bits for tree offsets: %u", offset_bits));
372  }
373  size=elements*2-2;
374  DBUG_PRINT("info", ("tree size in uint16: %u", size));
375  DBUG_PRINT("info", ("tree size in bytes: %u",
376  size * (uint) sizeof(uint16)));
377 
378  for (end=ptr+size ; ptr < end ; ptr++)
379  {
380  if (get_bit(bit_buff))
381  {
382  *ptr= (uint16) get_bits(bit_buff,offset_bits);
383  if ((ptr + *ptr >= end) || !*ptr)
384  {
385  DBUG_PRINT("error", ("ERROR: illegal pointer in decode tree"));
386  DBUG_RETURN(1);
387  }
388  }
389  else
390  *ptr= (uint16) (IS_CHAR + (get_bits(bit_buff,char_bits) + min_chr));
391  }
392  skip_to_next_byte(bit_buff);
393 
394  decode_tree->table= *decode_table;
395  decode_tree->intervalls= *intervall_buff;
396  if (! intervall_length)
397  {
398  /* Byte value compression. ptr started from tmp_buff. */
399  /* Find longest Huffman code from begin to end of tree in bits. */
400  table_bits= find_longest_bitstream(tmp_buff, ptr);
401  if (table_bits >= OFFSET_TABLE_SIZE)
402  DBUG_RETURN(1);
403  if (table_bits > myisam_quick_table_bits)
404  table_bits=myisam_quick_table_bits;
405  DBUG_PRINT("info", ("table bits: %u", table_bits));
406 
407  next_free_offset= (1 << table_bits);
408  make_quick_table(*decode_table,tmp_buff,&next_free_offset,0,table_bits,
409  table_bits);
410  (*decode_table)+= next_free_offset;
411  decode_tree->quick_table_bits=table_bits;
412  }
413  else
414  {
415  /* Distinct column value compression. ptr started from *decode_table */
416  (*decode_table)=end;
417  /*
418  get_bits() moves some bytes to a cache buffer in advance. May need
419  to step back.
420  */
421  bit_buff->pos-= bit_buff->bits/8;
422  /* Copy the distinct column values from the buffer. */
423  memcpy(*intervall_buff,bit_buff->pos,(size_t) intervall_length);
424  (*intervall_buff)+=intervall_length;
425  bit_buff->pos+=intervall_length;
426  bit_buff->bits=0;
427  }
428  DBUG_RETURN(0);
429 }
430 
431 
432 /*
433  Make a quick_table for faster decoding.
434 
435  SYNOPSIS
436  make_quick_table()
437  to_table Target quick_table and remaining decode table.
438  decode_table Source Huffman (sub-)tree within tmp_buff.
439  next_free_offset IN/OUT Next free offset from to_table.
440  Starts behind quick_table on the top-level.
441  value Huffman bits found so far.
442  bits Remaining bits to be collected.
443  max_bits Total number of bits to collect (table_bits).
444 
445  DESCRIPTION
446 
447  The quick table is an array of 16-bit values. There exists one value
448  for each possible code representable by max_bits (table_bits) bits.
449  In most cases table_bits is 9. So there are 512 16-bit values.
450 
451  If the high-order bit (16) is set (IS_CHAR) then the array slot for
452  this value is a valid Huffman code for a resulting byte value.
453 
454  The low-order 8 bits (1..8) are the resulting byte value.
455 
456  Bits 9..14 are the length of the Huffman code for this byte value.
457  This means so many bits from the input stream were needed to
458  represent this byte value. The remaining bits belong to later
459  Huffman codes. This also means that for every Huffman code shorter
460  than table_bits there are multiple entires in the array, which
461  differ just in the unused bits.
462 
463  If the high-order bit (16) is clear (0) then the remaining bits are
464  the position of the remaining Huffman decode tree segment behind the
465  quick table.
466 
467  RETURN
468  void
469 */
470 
471 static void make_quick_table(uint16 *to_table, uint16 *decode_table,
472  uint *next_free_offset, uint value, uint bits,
473  uint max_bits)
474 {
475  DBUG_ENTER("make_quick_table");
476 
477  /*
478  When down the table to the requested maximum, copy the rest of the
479  Huffman table.
480  */
481  if (!bits--)
482  {
483  /*
484  Remaining left Huffman tree segment starts behind quick table.
485  Remaining right Huffman tree segment starts behind left segment.
486  */
487  to_table[value]= (uint16) *next_free_offset;
488  /*
489  Re-construct the remaining Huffman tree segment at
490  next_free_offset in to_table.
491  */
492  *next_free_offset= copy_decode_table(to_table, *next_free_offset,
493  decode_table);
494  DBUG_VOID_RETURN;
495  }
496 
497  /* Descent on the left side. Left side bits are clear (0). */
498  if (!(*decode_table & IS_CHAR))
499  {
500  /* Not a leaf. Follow the pointer. */
501  make_quick_table(to_table, decode_table + *decode_table,
502  next_free_offset, value, bits, max_bits);
503  }
504  else
505  {
506  /*
507  A leaf. A Huffman code is complete. Fill the quick_table
508  array for all possible bit strings starting with this Huffman
509  code.
510  */
511  fill_quick_table(to_table + value, bits, max_bits, (uint) *decode_table);
512  }
513 
514  /* Descent on the right side. Right side bits are set (1). */
515  decode_table++;
516  value|= (1 << bits);
517  if (!(*decode_table & IS_CHAR))
518  {
519  /* Not a leaf. Follow the pointer. */
520  make_quick_table(to_table, decode_table + *decode_table,
521  next_free_offset, value, bits, max_bits);
522  }
523  else
524  {
525  /*
526  A leaf. A Huffman code is complete. Fill the quick_table
527  array for all possible bit strings starting with this Huffman
528  code.
529  */
530  fill_quick_table(to_table + value, bits, max_bits, (uint) *decode_table);
531  }
532 
533  DBUG_VOID_RETURN;
534 }
535 
536 
537 /*
538  Fill quick_table for all possible values starting with this Huffman code.
539 
540  SYNOPSIS
541  fill_quick_table()
542  table Target quick_table position.
543  bits Unused bits from max_bits.
544  max_bits Total number of bits to collect (table_bits).
545  value The byte encoded by the found Huffman code.
546 
547  DESCRIPTION
548 
549  Fill the segment (all slots) of the quick_table array with the
550  resulting value for the found Huffman code. There are as many slots
551  as there are combinations representable by the unused bits.
552 
553  In most cases we use 9 table bits. Assume a 3-bit Huffman code. Then
554  there are 6 unused bits. Hence we fill 2**6 = 64 slots with the
555  value.
556 
557  RETURN
558  void
559 */
560 
561 static void fill_quick_table(uint16 *table, uint bits, uint max_bits,
562  uint value)
563 {
564  uint16 *end;
565  DBUG_ENTER("fill_quick_table");
566 
567  /*
568  Bits 1..8 of value represent the decoded byte value.
569  Bits 9..14 become the length of the Huffman code for this byte value.
570  Bit 16 flags a valid code (IS_CHAR).
571  */
572  value|= (max_bits - bits) << 8 | IS_CHAR;
573 
574  for (end= table + ((my_ptrdiff_t) 1 << bits); table < end; table++)
575  {
576  *table= (uint16) value;
577  }
578  DBUG_VOID_RETURN;
579 }
580 
581 
582 /*
583  Reconstruct a decode subtree at the target position.
584 
585  SYNOPSIS
586  copy_decode_table()
587  to_pos Target quick_table and remaining decode table.
588  offset Next free offset from to_pos.
589  decode_table Source Huffman subtree within tmp_buff.
590 
591  NOTE
592  Pointers in the decode tree are relative to the pointers position.
593 
594  RETURN
595  next free offset from to_pos.
596 */
597 
598 static uint copy_decode_table(uint16 *to_pos, uint offset,
599  uint16 *decode_table)
600 {
601  uint prev_offset= offset;
602  DBUG_ENTER("copy_decode_table");
603 
604  /* Descent on the left side. */
605  if (!(*decode_table & IS_CHAR))
606  {
607  /* Set a pointer to the next target node. */
608  to_pos[offset]=2;
609  /* Copy the left hand subtree there. */
610  offset=copy_decode_table(to_pos,offset+2,decode_table+ *decode_table);
611  }
612  else
613  {
614  /* Copy the byte value. */
615  to_pos[offset]= *decode_table;
616  /* Step behind this node. */
617  offset+=2;
618  }
619 
620  /* Descent on the right side. */
621  decode_table++;
622  if (!(*decode_table & IS_CHAR))
623  {
624  /* Set a pointer to the next free target node. */
625  to_pos[prev_offset+1]=(uint16) (offset-prev_offset-1);
626  /* Copy the right hand subtree to the entry of that node. */
627  offset=copy_decode_table(to_pos,offset,decode_table+ *decode_table);
628  }
629  else
630  {
631  /* Copy the byte value. */
632  to_pos[prev_offset+1]= *decode_table;
633  }
634  DBUG_RETURN(offset);
635 }
636 
637 
638 /*
639  Find the length of the longest Huffman code in this table in bits.
640 
641  SYNOPSIS
642  find_longest_bitstream()
643  table Code (sub-)table start.
644  end End of code table.
645 
646  IMPLEMENTATION
647 
648  Recursively follow the branch(es) of the code pair on every level of
649  the tree until two byte values (and no branch) are found. Add one to
650  each level when returning back from each recursion stage.
651 
652  'end' is used for error checking only. A clean tree terminates
653  before reaching 'end'. Hence the exact value of 'end' is not too
654  important. However having it higher than necessary could lead to
655  misbehaviour should 'next' jump into the dirty area.
656 
657  RETURN
658  length Length of longest Huffman code in bits.
659  >= OFFSET_TABLE_SIZE Error, broken tree. It does not end before 'end'.
660 */
661 
662 static uint find_longest_bitstream(uint16 *table, uint16 *end)
663 {
664  uint length= 1;
665  uint length2;
666 
667  if (!(*table & IS_CHAR))
668  {
669  uint16 *next= table + *table;
670  if (next > end || next == table)
671  {
672  DBUG_PRINT("error", ("ERROR: illegal pointer in decode tree"));
673  return OFFSET_TABLE_SIZE;
674  }
675  length= find_longest_bitstream(next, end) + 1;
676  }
677  table++;
678  if (!(*table & IS_CHAR))
679  {
680  uint16 *next= table + *table;
681  if (next > end || next == table)
682  {
683  DBUG_PRINT("error", ("ERROR: illegal pointer in decode tree"));
684  return OFFSET_TABLE_SIZE;
685  }
686  length2= find_longest_bitstream(next, end) + 1;
687  length= MY_MAX(length, length2);
688  }
689  return length;
690 }
691 
692 
693 /*
694  Read record from datafile.
695 
696  SYNOPSIS
697  _mi_read_pack_record()
698  info A pointer to MI_INFO.
699  filepos File offset of the record.
700  buf RETURN The buffer to receive the record.
701 
702  RETURN
703  0 on success
704  HA_ERR_WRONG_IN_RECORD or -1 on error
705 */
706 
707 int _mi_read_pack_record(MI_INFO *info, my_off_t filepos, uchar *buf)
708 {
709  MI_BLOCK_INFO block_info;
710  File file;
711  DBUG_ENTER("mi_read_pack_record");
712 
713  if (filepos == HA_OFFSET_ERROR)
714  DBUG_RETURN(-1); /* _search() didn't find record */
715 
716  file=info->dfile;
717  if (_mi_pack_get_block_info(info, &info->bit_buff, &block_info,
718  &info->rec_buff, file, filepos))
719  goto err;
720  if (mysql_file_read(file, (uchar*) info->rec_buff + block_info.offset,
721  block_info.rec_len - block_info.offset, MYF(MY_NABP)))
722  goto panic;
723  info->update|= HA_STATE_AKTIV;
724  DBUG_RETURN(_mi_pack_rec_unpack(info, &info->bit_buff, buf,
725  info->rec_buff, block_info.rec_len));
726 panic:
727  my_errno=HA_ERR_WRONG_IN_RECORD;
728 err:
729  DBUG_RETURN(-1);
730 }
731 
732 
733 
734 int _mi_pack_rec_unpack(register MI_INFO *info, MI_BIT_BUFF *bit_buff,
735  register uchar *to, uchar *from, ulong reclength)
736 {
737  uchar *end_field;
738  reg3 MI_COLUMNDEF *end;
739  MI_COLUMNDEF *current_field;
740  MYISAM_SHARE *share=info->s;
741  DBUG_ENTER("_mi_pack_rec_unpack");
742 
743  init_bit_buffer(bit_buff, (uchar*) from, reclength);
744 
745  for (current_field=share->rec, end=current_field+share->base.fields ;
746  current_field < end ;
747  current_field++,to=end_field)
748  {
749  end_field=to+current_field->length;
750  (*current_field->unpack)(current_field, bit_buff, (uchar*) to,
751  (uchar*) end_field);
752  }
753  if (!bit_buff->error &&
754  bit_buff->pos - bit_buff->bits / 8 == bit_buff->end)
755  DBUG_RETURN(0);
756  info->update&= ~HA_STATE_AKTIV;
757  DBUG_RETURN(my_errno=HA_ERR_WRONG_IN_RECORD);
758 } /* _mi_pack_rec_unpack */
759 
760 
761  /* Return function to unpack field */
762 
763 static void (*get_unpack_function(MI_COLUMNDEF *rec))
764 (MI_COLUMNDEF *, MI_BIT_BUFF *, uchar *, uchar *)
765 {
766  switch (rec->base_type) {
767  case FIELD_SKIP_ZERO:
768  if (rec->pack_type & PACK_TYPE_ZERO_FILL)
769  return &uf_zerofill_skip_zero;
770  return &uf_skip_zero;
771  case FIELD_NORMAL:
772  if (rec->pack_type & PACK_TYPE_SPACE_FIELDS)
773  return &uf_space_normal;
774  if (rec->pack_type & PACK_TYPE_ZERO_FILL)
775  return &uf_zerofill_normal;
776  return &decode_bytes;
777  case FIELD_SKIP_ENDSPACE:
778  if (rec->pack_type & PACK_TYPE_SPACE_FIELDS)
779  {
780  if (rec->pack_type & PACK_TYPE_SELECTED)
781  return &uf_space_endspace_selected;
782  return &uf_space_endspace;
783  }
784  if (rec->pack_type & PACK_TYPE_SELECTED)
785  return &uf_endspace_selected;
786  return &uf_endspace;
787  case FIELD_SKIP_PRESPACE:
788  if (rec->pack_type & PACK_TYPE_SPACE_FIELDS)
789  {
790  if (rec->pack_type & PACK_TYPE_SELECTED)
791  return &uf_space_prespace_selected;
792  return &uf_space_prespace;
793  }
794  if (rec->pack_type & PACK_TYPE_SELECTED)
795  return &uf_prespace_selected;
796  return &uf_prespace;
797  case FIELD_CONSTANT:
798  return &uf_constant;
799  case FIELD_INTERVALL:
800  return &uf_intervall;
801  case FIELD_ZERO:
802  case FIELD_CHECK:
803  return &uf_zero;
804  case FIELD_BLOB:
805  return &uf_blob;
806  case FIELD_VARCHAR:
807  if (rec->length <= 256) /* 255 + 1 byte length */
808  return &uf_varchar1;
809  return &uf_varchar2;
810  case FIELD_LAST:
811  default:
812  return 0; /* This should never happend */
813  }
814 }
815 
816  /* The different functions to unpack a field */
817 
818 static void uf_zerofill_skip_zero(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
819  uchar *to, uchar *end)
820 {
821  if (get_bit(bit_buff))
822  memset(to, 0, (end-to));
823  else
824  {
825  end-=rec->space_length_bits;
826  decode_bytes(rec,bit_buff,to,end);
827  memset(end, 0, rec->space_length_bits);
828  }
829 }
830 
831 static void uf_skip_zero(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
832  uchar *end)
833 {
834  if (get_bit(bit_buff))
835  memset(to, 0, (end-to));
836  else
837  decode_bytes(rec,bit_buff,to,end);
838 }
839 
840 static void uf_space_normal(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
841  uchar *end)
842 {
843  if (get_bit(bit_buff))
844  memset(to, ' ', end - to);
845  else
846  decode_bytes(rec,bit_buff,to,end);
847 }
848 
849 static void uf_space_endspace_selected(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
850  uchar *to, uchar *end)
851 {
852  uint spaces;
853  if (get_bit(bit_buff))
854  memset(to, ' ', end-to);
855  else
856  {
857  if (get_bit(bit_buff))
858  {
859  if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
860  {
861  bit_buff->error=1;
862  return;
863  }
864  if (to+spaces != end)
865  decode_bytes(rec,bit_buff,to,end-spaces);
866  memset(end-spaces, ' ', spaces);
867  }
868  else
869  decode_bytes(rec,bit_buff,to,end);
870  }
871 }
872 
873 static void uf_endspace_selected(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
874  uchar *to, uchar *end)
875 {
876  uint spaces;
877  if (get_bit(bit_buff))
878  {
879  if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
880  {
881  bit_buff->error=1;
882  return;
883  }
884  if (to+spaces != end)
885  decode_bytes(rec,bit_buff,to,end-spaces);
886  memset(end - spaces, ' ', spaces);
887  }
888  else
889  decode_bytes(rec,bit_buff,to,end);
890 }
891 
892 static void uf_space_endspace(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
893  uchar *end)
894 {
895  uint spaces;
896  if (get_bit(bit_buff))
897  memset(to, ' ', end - to);
898  else
899  {
900  if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
901  {
902  bit_buff->error=1;
903  return;
904  }
905  if (to+spaces != end)
906  decode_bytes(rec,bit_buff,to,end-spaces);
907  memset(end - spaces, ' ', spaces);
908  }
909 }
910 
911 static void uf_endspace(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
912  uchar *end)
913 {
914  uint spaces;
915  if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
916  {
917  bit_buff->error=1;
918  return;
919  }
920  if (to+spaces != end)
921  decode_bytes(rec,bit_buff,to,end-spaces);
922  memset(end - spaces, ' ', spaces);
923 }
924 
925 static void uf_space_prespace_selected(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
926  uchar *to, uchar *end)
927 {
928  uint spaces;
929  if (get_bit(bit_buff))
930  memset(to, ' ', end - to);
931  else
932  {
933  if (get_bit(bit_buff))
934  {
935  if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
936  {
937  bit_buff->error=1;
938  return;
939  }
940  memset(to, ' ', spaces);
941  if (to+spaces != end)
942  decode_bytes(rec,bit_buff,to+spaces,end);
943  }
944  else
945  decode_bytes(rec,bit_buff,to,end);
946  }
947 }
948 
949 
950 static void uf_prespace_selected(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
951  uchar *to, uchar *end)
952 {
953  uint spaces;
954  if (get_bit(bit_buff))
955  {
956  if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
957  {
958  bit_buff->error=1;
959  return;
960  }
961  memset(to, ' ', spaces);
962  if (to+spaces != end)
963  decode_bytes(rec,bit_buff,to+spaces,end);
964  }
965  else
966  decode_bytes(rec,bit_buff,to,end);
967 }
968 
969 
970 static void uf_space_prespace(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
971  uchar *end)
972 {
973  uint spaces;
974  if (get_bit(bit_buff))
975  memset(to, ' ', end-to);
976  else
977  {
978  if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
979  {
980  bit_buff->error=1;
981  return;
982  }
983  memset(to, ' ', spaces);
984  if (to+spaces != end)
985  decode_bytes(rec,bit_buff,to+spaces,end);
986  }
987 }
988 
989 static void uf_prespace(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
990  uchar *end)
991 {
992  uint spaces;
993  if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
994  {
995  bit_buff->error=1;
996  return;
997  }
998  memset(to, ' ', spaces);
999  if (to+spaces != end)
1000  decode_bytes(rec,bit_buff,to+spaces,end);
1001 }
1002 
1003 static void uf_zerofill_normal(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
1004  uchar *end)
1005 {
1006  end-=rec->space_length_bits;
1007  decode_bytes(rec,bit_buff,(uchar*) to,end);
1008  memset(end, 0, rec->space_length_bits);
1009 }
1010 
1011 static void uf_constant(MI_COLUMNDEF *rec,
1012  MI_BIT_BUFF *bit_buff __attribute__((unused)),
1013  uchar *to,
1014  uchar *end)
1015 {
1016  memcpy(to,rec->huff_tree->intervalls,(size_t) (end-to));
1017 }
1018 
1019 static void uf_intervall(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
1020  uchar *end)
1021 {
1022  reg1 uint field_length=(uint) (end-to);
1023  memcpy(to,rec->huff_tree->intervalls+field_length*decode_pos(bit_buff,
1024  rec->huff_tree),
1025  (size_t) field_length);
1026 }
1027 
1028 
1029 /*ARGSUSED*/
1030 static void uf_zero(MI_COLUMNDEF *rec __attribute__((unused)),
1031  MI_BIT_BUFF *bit_buff __attribute__((unused)),
1032  uchar *to, uchar *end)
1033 {
1034  memset(to, 0, (end-to));
1035 }
1036 
1037 static void uf_blob(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
1038  uchar *to, uchar *end)
1039 {
1040  if (get_bit(bit_buff))
1041  memset(to, 0, (end-to));
1042  else
1043  {
1044  ulong length=get_bits(bit_buff,rec->space_length_bits);
1045  uint pack_length=(uint) (end-to)-portable_sizeof_char_ptr;
1046  if (bit_buff->blob_pos+length > bit_buff->blob_end)
1047  {
1048  bit_buff->error=1;
1049  memset(to, 0, (end-to));
1050  return;
1051  }
1052  decode_bytes(rec,bit_buff,bit_buff->blob_pos,bit_buff->blob_pos+length);
1053  _mi_store_blob_length((uchar*) to,pack_length,length);
1054  memcpy(to+pack_length, &bit_buff->blob_pos, sizeof(char*));
1055  bit_buff->blob_pos+=length;
1056  }
1057 }
1058 
1059 
1060 static void uf_varchar1(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
1061  uchar *to, uchar *end __attribute__((unused)))
1062 {
1063  if (get_bit(bit_buff))
1064  to[0]= 0; /* Zero lengths */
1065  else
1066  {
1067  ulong length=get_bits(bit_buff,rec->space_length_bits);
1068  *to= (uchar) length;
1069  decode_bytes(rec,bit_buff,to+1,to+1+length);
1070  }
1071 }
1072 
1073 
1074 static void uf_varchar2(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
1075  uchar *to, uchar *end __attribute__((unused)))
1076 {
1077  if (get_bit(bit_buff))
1078  to[0]=to[1]=0; /* Zero lengths */
1079  else
1080  {
1081  ulong length=get_bits(bit_buff,rec->space_length_bits);
1082  int2store(to,length);
1083  decode_bytes(rec,bit_buff,to+2,to+2+length);
1084  }
1085 }
1086 
1087  /* Functions to decode of buffer of bits */
1088 
1089 #if BITS_SAVED == 64
1090 
1091 static void decode_bytes(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,uchar *to,
1092  uchar *end)
1093 {
1094  reg1 uint bits,low_byte;
1095  reg3 uint16 *pos;
1096  reg4 uint table_bits,table_and;
1097  MI_DECODE_TREE *decode_tree;
1098 
1099  decode_tree=rec->decode_tree;
1100  bits=bit_buff->bits; /* Save in reg for quicker access */
1101  table_bits=decode_tree->quick_table_bits;
1102  table_and= (1 << table_bits)-1;
1103 
1104  do
1105  {
1106  if (bits <= 32)
1107  {
1108  if (bit_buff->pos > bit_buff->end+4)
1109  {
1110  bit_buff->error=1;
1111  return; /* Can't be right */
1112  }
1113  bit_buff->current_byte= (bit_buff->current_byte << 32) +
1114  ((((uint) bit_buff->pos[3])) +
1115  (((uint) bit_buff->pos[2]) << 8) +
1116  (((uint) bit_buff->pos[1]) << 16) +
1117  (((uint) bit_buff->pos[0]) << 24));
1118  bit_buff->pos+=4;
1119  bits+=32;
1120  }
1121  /*
1122  First use info in quick_table.
1123 
1124  The quick table is an array of 16-bit values. There exists one
1125  value for each possible code representable by table_bits bits.
1126  In most cases table_bits is 9. So there are 512 16-bit values.
1127 
1128  If the high-order bit (16) is set (IS_CHAR) then the array slot
1129  for this value is a valid Huffman code for a resulting byte value.
1130 
1131  The low-order 8 bits (1..8) are the resulting byte value.
1132 
1133  Bits 9..14 are the length of the Huffman code for this byte value.
1134  This means so many bits from the input stream were needed to
1135  represent this byte value. The remaining bits belong to later
1136  Huffman codes. This also means that for every Huffman code shorter
1137  than table_bits there are multiple entires in the array, which
1138  differ just in the unused bits.
1139 
1140  If the high-order bit (16) is clear (0) then the remaining bits are
1141  the position of the remaining Huffman decode tree segment behind the
1142  quick table.
1143  */
1144  low_byte=(uint) (bit_buff->current_byte >> (bits - table_bits)) & table_and;
1145  low_byte=decode_tree->table[low_byte];
1146  if (low_byte & IS_CHAR)
1147  {
1148  /*
1149  All Huffman codes of less or equal table_bits length are in the
1150  quick table. This is one of them.
1151  */
1152  *to++ = (low_byte & 255); /* Found char in quick table */
1153  bits-= ((low_byte >> 8) & 31); /* Remove bits used */
1154  }
1155  else
1156  { /* Map through rest of decode-table */
1157  /* This means that the Huffman code must be longer than table_bits. */
1158  pos=decode_tree->table+low_byte;
1159  bits-=table_bits;
1160  /* NOTE: decode_bytes_test_bit() is a macro wich contains a break !!! */
1161  for (;;)
1162  {
1163  low_byte=(uint) (bit_buff->current_byte >> (bits-8));
1164  decode_bytes_test_bit(0);
1165  decode_bytes_test_bit(1);
1166  decode_bytes_test_bit(2);
1167  decode_bytes_test_bit(3);
1168  decode_bytes_test_bit(4);
1169  decode_bytes_test_bit(5);
1170  decode_bytes_test_bit(6);
1171  decode_bytes_test_bit(7);
1172  bits-=8;
1173  }
1174  *to++ = *pos;
1175  }
1176  } while (to != end);
1177 
1178  bit_buff->bits=bits;
1179  return;
1180 }
1181 
1182 #else
1183 
1184 static void decode_bytes(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
1185  uchar *end)
1186 {
1187  reg1 uint bits,low_byte;
1188  reg3 uint16 *pos;
1189  reg4 uint table_bits,table_and;
1190  MI_DECODE_TREE *decode_tree;
1191 
1192  decode_tree=rec->huff_tree;
1193  bits=bit_buff->bits; /* Save in reg for quicker access */
1194  table_bits=decode_tree->quick_table_bits;
1195  table_and= (1 << table_bits)-1;
1196 
1197  do
1198  {
1199  if (bits < table_bits)
1200  {
1201  if (bit_buff->pos > bit_buff->end+1)
1202  {
1203  bit_buff->error=1;
1204  return; /* Can't be right */
1205  }
1206 #if BITS_SAVED == 32
1207  bit_buff->current_byte= (bit_buff->current_byte << 24) +
1208  (((uint) ((uchar) bit_buff->pos[2]))) +
1209  (((uint) ((uchar) bit_buff->pos[1])) << 8) +
1210  (((uint) ((uchar) bit_buff->pos[0])) << 16);
1211  bit_buff->pos+=3;
1212  bits+=24;
1213 #else
1214  if (bits) /* We must have at leasts 9 bits */
1215  {
1216  bit_buff->current_byte= (bit_buff->current_byte << 8) +
1217  (uint) ((uchar) bit_buff->pos[0]);
1218  bit_buff->pos++;
1219  bits+=8;
1220  }
1221  else
1222  {
1223  bit_buff->current_byte= ((uint) ((uchar) bit_buff->pos[0]) << 8) +
1224  ((uint) ((uchar) bit_buff->pos[1]));
1225  bit_buff->pos+=2;
1226  bits+=16;
1227  }
1228 #endif
1229  }
1230  /* First use info in quick_table */
1231  low_byte=(bit_buff->current_byte >> (bits - table_bits)) & table_and;
1232  low_byte=decode_tree->table[low_byte];
1233  if (low_byte & IS_CHAR)
1234  {
1235  *to++ = (low_byte & 255); /* Found char in quick table */
1236  bits-= ((low_byte >> 8) & 31); /* Remove bits used */
1237  }
1238  else
1239  { /* Map through rest of decode-table */
1240  pos=decode_tree->table+low_byte;
1241  bits-=table_bits;
1242  for (;;)
1243  {
1244  if (bits < 8)
1245  { /* We don't need to check end */
1246 #if BITS_SAVED == 32
1247  bit_buff->current_byte= (bit_buff->current_byte << 24) +
1248  (((uint) ((uchar) bit_buff->pos[2]))) +
1249  (((uint) ((uchar) bit_buff->pos[1])) << 8) +
1250  (((uint) ((uchar) bit_buff->pos[0])) << 16);
1251  bit_buff->pos+=3;
1252  bits+=24;
1253 #else
1254  bit_buff->current_byte= (bit_buff->current_byte << 8) +
1255  (uint) ((uchar) bit_buff->pos[0]);
1256  bit_buff->pos+=1;
1257  bits+=8;
1258 #endif
1259  }
1260  low_byte=(uint) (bit_buff->current_byte >> (bits-8));
1261  decode_bytes_test_bit(0);
1262  decode_bytes_test_bit(1);
1263  decode_bytes_test_bit(2);
1264  decode_bytes_test_bit(3);
1265  decode_bytes_test_bit(4);
1266  decode_bytes_test_bit(5);
1267  decode_bytes_test_bit(6);
1268  decode_bytes_test_bit(7);
1269  bits-=8;
1270  }
1271  *to++ = (uchar) *pos;
1272  }
1273  } while (to != end);
1274 
1275  bit_buff->bits=bits;
1276  return;
1277 }
1278 #endif /* BIT_SAVED == 64 */
1279 
1280 
1281 static uint decode_pos(MI_BIT_BUFF *bit_buff, MI_DECODE_TREE *decode_tree)
1282 {
1283  uint16 *pos=decode_tree->table;
1284  for (;;)
1285  {
1286  if (get_bit(bit_buff))
1287  pos++;
1288  if (*pos & IS_CHAR)
1289  return (uint) (*pos & ~IS_CHAR);
1290  pos+= *pos;
1291  }
1292 }
1293 
1294 
1295 int _mi_read_rnd_pack_record(MI_INFO *info, uchar *buf,
1296  register my_off_t filepos,
1297  my_bool skip_deleted_blocks)
1298 {
1299  uint b_type;
1300  MI_BLOCK_INFO block_info;
1301  MYISAM_SHARE *share=info->s;
1302  DBUG_ENTER("_mi_read_rnd_pack_record");
1303 
1304  if (filepos >= info->state->data_file_length)
1305  {
1306  my_errno= HA_ERR_END_OF_FILE;
1307  goto err;
1308  }
1309 
1310  if (info->opt_flag & READ_CACHE_USED)
1311  {
1312  if (_mi_read_cache(&info->rec_cache, (uchar*) block_info.header,
1313  filepos, share->pack.ref_length,
1314  skip_deleted_blocks ? READING_NEXT : 0))
1315  goto err;
1316  b_type=_mi_pack_get_block_info(info, &info->bit_buff, &block_info,
1317  &info->rec_buff, -1, filepos);
1318  }
1319  else
1320  b_type=_mi_pack_get_block_info(info, &info->bit_buff, &block_info,
1321  &info->rec_buff, info->dfile, filepos);
1322  if (b_type)
1323  goto err; /* Error code is already set */
1324 #ifndef DBUG_OFF
1325  if (block_info.rec_len > share->max_pack_length)
1326  {
1327  my_errno=HA_ERR_WRONG_IN_RECORD;
1328  goto err;
1329  }
1330 #endif
1331 
1332  if (info->opt_flag & READ_CACHE_USED)
1333  {
1334  if (_mi_read_cache(&info->rec_cache, (uchar*) info->rec_buff,
1335  block_info.filepos, block_info.rec_len,
1336  skip_deleted_blocks ? READING_NEXT : 0))
1337  goto err;
1338  }
1339  else
1340  {
1341  if (mysql_file_read(info->dfile,
1342  (uchar*) info->rec_buff + block_info.offset,
1343  block_info.rec_len-block_info.offset, MYF(MY_NABP)))
1344  goto err;
1345  }
1346  info->packed_length=block_info.rec_len;
1347  info->lastpos=filepos;
1348  info->nextpos=block_info.filepos+block_info.rec_len;
1349  info->update|= HA_STATE_AKTIV | HA_STATE_KEY_CHANGED;
1350 
1351  DBUG_RETURN (_mi_pack_rec_unpack(info, &info->bit_buff, buf,
1352  info->rec_buff, block_info.rec_len));
1353  err:
1354  DBUG_RETURN(my_errno);
1355 }
1356 
1357 
1358  /* Read and process header from a huff-record-file */
1359 
1360 uint _mi_pack_get_block_info(MI_INFO *myisam, MI_BIT_BUFF *bit_buff,
1361  MI_BLOCK_INFO *info, uchar **rec_buff_p,
1362  File file, my_off_t filepos)
1363 {
1364  uchar *header=info->header;
1365  uint head_length, UNINIT_VAR(ref_length);
1366  LINT_INIT(ref_length);
1367 
1368  if (file >= 0)
1369  {
1370  ref_length=myisam->s->pack.ref_length;
1371  /*
1372  We can't use mysql_file_pread() here because mi_read_rnd_pack_record assumes
1373  position is ok
1374  */
1375  mysql_file_seek(file, filepos, MY_SEEK_SET, MYF(0));
1376  if (mysql_file_read(file, header, ref_length, MYF(MY_NABP)))
1377  return BLOCK_FATAL_ERROR;
1378  DBUG_DUMP("header",(uchar*) header,ref_length);
1379  }
1380  head_length= read_pack_length((uint) myisam->s->pack.version, header,
1381  &info->rec_len);
1382  if (myisam->s->base.blobs)
1383  {
1384  head_length+= read_pack_length((uint) myisam->s->pack.version,
1385  header + head_length, &info->blob_len);
1386  /*
1387  Ensure that the record buffer is big enough for the compressed
1388  record plus all expanded blobs. [We do not have an extra buffer
1389  for the resulting blobs. Sigh.]
1390  */
1391  if (!(mi_alloc_rec_buff(myisam,info->rec_len + info->blob_len,
1392  rec_buff_p)))
1393  return BLOCK_FATAL_ERROR; /* not enough memory */
1394  bit_buff->blob_pos= (uchar*) *rec_buff_p + info->rec_len;
1395  bit_buff->blob_end= bit_buff->blob_pos + info->blob_len;
1396  myisam->blob_length=info->blob_len;
1397  }
1398  info->filepos=filepos+head_length;
1399  if (file > 0)
1400  {
1401  info->offset= MY_MIN(info->rec_len, ref_length - head_length);
1402  memcpy(*rec_buff_p, header + head_length, info->offset);
1403  }
1404  return 0;
1405 }
1406 
1407 
1408  /* rutines for bit buffer */
1409  /* Note buffer must be 6 byte bigger than longest row */
1410 
1411 static void init_bit_buffer(MI_BIT_BUFF *bit_buff, uchar *buffer, uint length)
1412 {
1413  bit_buff->pos=buffer;
1414  bit_buff->end=buffer+length;
1415  bit_buff->bits=bit_buff->error=0;
1416  bit_buff->current_byte=0; /* Avoid purify errors */
1417 }
1418 
1419 static uint fill_and_get_bits(MI_BIT_BUFF *bit_buff, uint count)
1420 {
1421  uint tmp;
1422  count-=bit_buff->bits;
1423  tmp=(bit_buff->current_byte & mask[bit_buff->bits]) << count;
1424  fill_buffer(bit_buff);
1425  bit_buff->bits=BITS_SAVED - count;
1426  return tmp+(bit_buff->current_byte >> (BITS_SAVED - count));
1427 }
1428 
1429  /* Fill in empty bit_buff->current_byte from buffer */
1430  /* Sets bit_buff->error if buffer is exhausted */
1431 
1432 static void fill_buffer(MI_BIT_BUFF *bit_buff)
1433 {
1434  if (bit_buff->pos >= bit_buff->end)
1435  {
1436  bit_buff->error= 1;
1437  bit_buff->current_byte=0;
1438  return;
1439  }
1440 
1441 #if BITS_SAVED == 64
1442  bit_buff->current_byte= ((((uint) ((uchar) bit_buff->pos[7]))) +
1443  (((uint) ((uchar) bit_buff->pos[6])) << 8) +
1444  (((uint) ((uchar) bit_buff->pos[5])) << 16) +
1445  (((uint) ((uchar) bit_buff->pos[4])) << 24) +
1446  ((ulonglong)
1447  ((((uint) ((uchar) bit_buff->pos[3]))) +
1448  (((uint) ((uchar) bit_buff->pos[2])) << 8) +
1449  (((uint) ((uchar) bit_buff->pos[1])) << 16) +
1450  (((uint) ((uchar) bit_buff->pos[0])) << 24)) << 32));
1451  bit_buff->pos+=8;
1452 #else
1453 #if BITS_SAVED == 32
1454  bit_buff->current_byte= (((uint) ((uchar) bit_buff->pos[3])) +
1455  (((uint) ((uchar) bit_buff->pos[2])) << 8) +
1456  (((uint) ((uchar) bit_buff->pos[1])) << 16) +
1457  (((uint) ((uchar) bit_buff->pos[0])) << 24));
1458  bit_buff->pos+=4;
1459 #else
1460  bit_buff->current_byte= (uint) (((uint) ((uchar) bit_buff->pos[1]))+
1461  (((uint) ((uchar) bit_buff->pos[0])) << 8));
1462  bit_buff->pos+=2;
1463 #endif
1464 #endif
1465 }
1466 
1467  /* Get number of bits neaded to represent value */
1468 
1469 static uint max_bit(register uint value)
1470 {
1471  reg2 uint power=1;
1472 
1473  while ((value>>=1))
1474  power++;
1475  return (power);
1476 }
1477 
1478 
1479 /*****************************************************************************
1480  Some redefined functions to handle files when we are using memmap
1481 *****************************************************************************/
1482 #ifdef HAVE_SYS_MMAN_H
1483 #include <sys/mman.h>
1484 #endif
1485 
1486 #ifdef HAVE_MMAP
1487 
1488 static int _mi_read_mempack_record(MI_INFO *info,my_off_t filepos,uchar *buf);
1489 static int _mi_read_rnd_mempack_record(MI_INFO*, uchar *,my_off_t, my_bool);
1490 
1491 my_bool _mi_memmap_file(MI_INFO *info)
1492 {
1493  MYISAM_SHARE *share=info->s;
1494  my_bool eom;
1495 
1496  DBUG_ENTER("mi_memmap_file");
1497 
1498  if (!info->s->file_map)
1499  {
1500  my_off_t data_file_length= share->state.state.data_file_length;
1501 
1502  if (myisam_mmap_size != SIZE_T_MAX)
1503  {
1504  mysql_mutex_lock(&THR_LOCK_myisam_mmap);
1505  eom= data_file_length > myisam_mmap_size - myisam_mmap_used - MEMMAP_EXTRA_MARGIN;
1506  if (!eom)
1507  myisam_mmap_used+= data_file_length + MEMMAP_EXTRA_MARGIN;
1508  mysql_mutex_unlock(&THR_LOCK_myisam_mmap);
1509  }
1510  else
1511  eom= data_file_length > myisam_mmap_size - MEMMAP_EXTRA_MARGIN;
1512 
1513  if (eom)
1514  {
1515  DBUG_PRINT("warning", ("File is too large for mmap"));
1516  DBUG_RETURN(0);
1517  }
1518  if (mysql_file_seek(info->dfile, 0L, MY_SEEK_END, MYF(0)) <
1519  share->state.state.data_file_length+MEMMAP_EXTRA_MARGIN)
1520  {
1521  DBUG_PRINT("warning",("File isn't extended for memmap"));
1522  if (myisam_mmap_size != SIZE_T_MAX)
1523  {
1524  mysql_mutex_lock(&THR_LOCK_myisam_mmap);
1525  myisam_mmap_used-= data_file_length + MEMMAP_EXTRA_MARGIN;
1526  mysql_mutex_unlock(&THR_LOCK_myisam_mmap);
1527  }
1528  DBUG_RETURN(0);
1529  }
1530  if (mi_dynmap_file(info,
1531  share->state.state.data_file_length +
1532  MEMMAP_EXTRA_MARGIN))
1533  {
1534  if (myisam_mmap_size != SIZE_T_MAX)
1535  {
1536  mysql_mutex_lock(&THR_LOCK_myisam_mmap);
1537  myisam_mmap_used-= data_file_length + MEMMAP_EXTRA_MARGIN;
1538  mysql_mutex_unlock(&THR_LOCK_myisam_mmap);
1539  }
1540  DBUG_RETURN(0);
1541  }
1542  }
1543  info->opt_flag|= MEMMAP_USED;
1544  info->read_record= share->read_record= _mi_read_mempack_record;
1545  share->read_rnd= _mi_read_rnd_mempack_record;
1546  DBUG_RETURN(1);
1547 }
1548 
1549 
1550 void _mi_unmap_file(MI_INFO *info)
1551 {
1552  DBUG_ASSERT(info->s->options & HA_OPTION_COMPRESS_RECORD);
1553 
1554  (void) my_munmap((char*) info->s->file_map, (size_t) info->s->mmaped_length);
1555 
1556  if (myisam_mmap_size != SIZE_T_MAX)
1557  {
1558  mysql_mutex_lock(&THR_LOCK_myisam_mmap);
1559  myisam_mmap_used-= info->s->mmaped_length;
1560  mysql_mutex_unlock(&THR_LOCK_myisam_mmap);
1561  }
1562 }
1563 
1564 
1565 static uchar *_mi_mempack_get_block_info(MI_INFO *myisam, MI_BIT_BUFF *bit_buff,
1566  MI_BLOCK_INFO *info, uchar **rec_buff_p,
1567  uchar *header)
1568 {
1569  header+= read_pack_length((uint) myisam->s->pack.version, header,
1570  &info->rec_len);
1571  if (myisam->s->base.blobs)
1572  {
1573  header+= read_pack_length((uint) myisam->s->pack.version, header,
1574  &info->blob_len);
1575  /* mi_alloc_rec_buff sets my_errno on error */
1576  if (!(mi_alloc_rec_buff(myisam, info->blob_len,
1577  rec_buff_p)))
1578  return 0; /* not enough memory */
1579  bit_buff->blob_pos= (uchar*) *rec_buff_p;
1580  bit_buff->blob_end= (uchar*) *rec_buff_p + info->blob_len;
1581  }
1582  return header;
1583 }
1584 
1585 
1586 static int _mi_read_mempack_record(MI_INFO *info, my_off_t filepos, uchar *buf)
1587 {
1588  MI_BLOCK_INFO block_info;
1589  MYISAM_SHARE *share=info->s;
1590  uchar *pos;
1591  DBUG_ENTER("mi_read_mempack_record");
1592 
1593  if (filepos == HA_OFFSET_ERROR)
1594  DBUG_RETURN(-1); /* _search() didn't find record */
1595 
1596  if (!(pos= (uchar*) _mi_mempack_get_block_info(info, &info->bit_buff,
1597  &block_info, &info->rec_buff,
1598  (uchar*) share->file_map+
1599  filepos)))
1600  DBUG_RETURN(-1);
1601  DBUG_RETURN(_mi_pack_rec_unpack(info, &info->bit_buff, buf,
1602  pos, block_info.rec_len));
1603 }
1604 
1605 
1606 /*ARGSUSED*/
1607 static int _mi_read_rnd_mempack_record(MI_INFO *info, uchar *buf,
1608  register my_off_t filepos,
1609  my_bool skip_deleted_blocks
1610  __attribute__((unused)))
1611 {
1612  MI_BLOCK_INFO block_info;
1613  MYISAM_SHARE *share=info->s;
1614  uchar *pos,*start;
1615  DBUG_ENTER("_mi_read_rnd_mempack_record");
1616 
1617  if (filepos >= share->state.state.data_file_length)
1618  {
1619  my_errno=HA_ERR_END_OF_FILE;
1620  goto err;
1621  }
1622  if (!(pos= (uchar*) _mi_mempack_get_block_info(info, &info->bit_buff,
1623  &block_info, &info->rec_buff,
1624  (uchar*)
1625  (start=share->file_map+
1626  filepos))))
1627  goto err;
1628 #ifndef DBUG_OFF
1629  if (block_info.rec_len > info->s->max_pack_length)
1630  {
1631  my_errno=HA_ERR_WRONG_IN_RECORD;
1632  goto err;
1633  }
1634 #endif
1635  info->packed_length=block_info.rec_len;
1636  info->lastpos=filepos;
1637  info->nextpos=filepos+(uint) (pos-start)+block_info.rec_len;
1638  info->update|= HA_STATE_AKTIV | HA_STATE_KEY_CHANGED;
1639 
1640  DBUG_RETURN (_mi_pack_rec_unpack(info, &info->bit_buff, buf,
1641  pos, block_info.rec_len));
1642  err:
1643  DBUG_RETURN(my_errno);
1644 }
1645 
1646 #endif /* HAVE_MMAP */
1647 
1648  /* Save length of row */
1649 
1650 uint save_pack_length(uint version, uchar *block_buff, ulong length)
1651 {
1652  if (length < 254)
1653  {
1654  *(uchar*) block_buff= (uchar) length;
1655  return 1;
1656  }
1657  if (length <= 65535)
1658  {
1659  *(uchar*) block_buff=254;
1660  int2store(block_buff+1,(uint) length);
1661  return 3;
1662  }
1663  *(uchar*) block_buff=255;
1664  if (version == 1) /* old format */
1665  {
1666  DBUG_ASSERT(length <= 0xFFFFFF);
1667  int3store(block_buff + 1, (ulong) length);
1668  return 4;
1669  }
1670  else
1671  {
1672  int4store(block_buff + 1, (ulong) length);
1673  return 5;
1674  }
1675 }
1676 
1677 
1678 uint read_pack_length(uint version, const uchar *buf, ulong *length)
1679 {
1680  if (buf[0] < 254)
1681  {
1682  *length= buf[0];
1683  return 1;
1684  }
1685  else if (buf[0] == 254)
1686  {
1687  *length= uint2korr(buf + 1);
1688  return 3;
1689  }
1690  if (version == 1) /* old format */
1691  {
1692  *length= uint3korr(buf + 1);
1693  return 4;
1694  }
1695  else
1696  {
1697  *length= uint4korr(buf + 1);
1698  return 5;
1699  }
1700 }
1701 
1702 
1703 uint calc_pack_length(uint version, ulong length)
1704 {
1705  return (length < 254) ? 1 : (length < 65536) ? 3 : (version == 1) ? 4 : 5;
1706 }