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