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