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