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