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