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