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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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 :
52 : static my_bool _ma_read_pack_info(MARIA_SHARE *share, File file,
53 : pbool fix_keys);
54 : static 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);
58 : static void make_quick_table(uint16 *to_table,uint16 *decode_table,
59 : uint *next_free,uint value,uint bits,
60 : uint max_bits);
61 : static void fill_quick_table(uint16 *table,uint bits, uint max_bits,
62 : uint value);
63 : static uint copy_decode_table(uint16 *to_pos,uint offset,
64 : uint16 *decode_table);
65 : static uint find_longest_bitstream(uint16 *table, uint16 *end);
66 : static void (*get_unpack_function(MARIA_COLUMNDEF *rec))(MARIA_COLUMNDEF *field,
67 : MARIA_BIT_BUFF *buff,
68 : uchar *to,
69 : uchar *end);
70 : static void uf_zerofill_skip_zero(MARIA_COLUMNDEF *rec,
71 : MARIA_BIT_BUFF *bit_buff,
72 : uchar *to,uchar *end);
73 : static void uf_skip_zero(MARIA_COLUMNDEF *rec,MARIA_BIT_BUFF *bit_buff,
74 : uchar *to,uchar *end);
75 : static void uf_space_normal(MARIA_COLUMNDEF *rec,MARIA_BIT_BUFF *bit_buff,
76 : uchar *to,uchar *end);
77 : static void uf_space_endspace_selected(MARIA_COLUMNDEF *rec,
78 : MARIA_BIT_BUFF *bit_buff,
79 : uchar *to, uchar *end);
80 : static void uf_endspace_selected(MARIA_COLUMNDEF *rec,MARIA_BIT_BUFF *bit_buff,
81 : uchar *to,uchar *end);
82 : static void uf_space_endspace(MARIA_COLUMNDEF *rec,MARIA_BIT_BUFF *bit_buff,
83 : uchar *to,uchar *end);
84 : static void uf_endspace(MARIA_COLUMNDEF *rec,MARIA_BIT_BUFF *bit_buff,
85 : uchar *to,uchar *end);
86 : static void uf_space_prespace_selected(MARIA_COLUMNDEF *rec,
87 : MARIA_BIT_BUFF *bit_buff,
88 : uchar *to, uchar *end);
89 : static void uf_prespace_selected(MARIA_COLUMNDEF *rec,MARIA_BIT_BUFF *bit_buff,
90 : uchar *to,uchar *end);
91 : static void uf_space_prespace(MARIA_COLUMNDEF *rec,MARIA_BIT_BUFF *bit_buff,
92 : uchar *to,uchar *end);
93 : static void uf_prespace(MARIA_COLUMNDEF *rec,MARIA_BIT_BUFF *bit_buff,
94 : uchar *to,uchar *end);
95 : static void uf_zerofill_normal(MARIA_COLUMNDEF *rec,MARIA_BIT_BUFF *bit_buff,
96 : uchar *to,uchar *end);
97 : static void uf_constant(MARIA_COLUMNDEF *rec,MARIA_BIT_BUFF *bit_buff,
98 : uchar *to,uchar *end);
99 : static void uf_intervall(MARIA_COLUMNDEF *rec,MARIA_BIT_BUFF *bit_buff,
100 : uchar *to,uchar *end);
101 : static void uf_zero(MARIA_COLUMNDEF *rec,MARIA_BIT_BUFF *bit_buff,
102 : uchar *to,uchar *end);
103 : static void uf_blob(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
104 : uchar *to, uchar *end);
105 : static void uf_varchar1(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
106 : uchar *to, uchar *end);
107 : static void uf_varchar2(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
108 : uchar *to, uchar *end);
109 : static void decode_bytes(MARIA_COLUMNDEF *rec,MARIA_BIT_BUFF *bit_buff,
110 : uchar *to,uchar *end);
111 : static uint decode_pos(MARIA_BIT_BUFF *bit_buff,
112 : MARIA_DECODE_TREE *decode_tree);
113 : static void init_bit_buffer(MARIA_BIT_BUFF *bit_buff,uchar *buffer,
114 : uint length);
115 : static uint fill_and_get_bits(MARIA_BIT_BUFF *bit_buff,uint count);
116 : static void fill_buffer(MARIA_BIT_BUFF *bit_buff);
117 : static uint max_bit(uint value);
118 : static uint read_pack_length(uint version, const uchar *buf, ulong *length);
119 : #ifdef HAVE_MMAP
120 : static 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 :
128 : static 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 :
144 : my_bool _ma_once_init_pack_row(MARIA_SHARE *share, File dfile)
145 0 : {
146 0 : share->options|= HA_OPTION_READ_ONLY_DATA;
147 0 : return (_ma_read_pack_info(share, dfile,
148 : (pbool)
149 : test(!(share->options &
150 : (HA_OPTION_PACK_RECORD |
151 : HA_OPTION_TEMP_COMPRESS_RECORD)))));
152 : }
153 :
154 :
155 : my_bool _ma_once_end_pack_row(MARIA_SHARE *share)
156 0 : {
157 0 : if (share->decode_trees)
158 : {
159 0 : my_free(share->decode_trees,MYF(0));
160 0 : my_free(share->decode_tables,MYF(0));
161 : }
162 0 : return 0;
163 : }
164 :
165 :
166 : /* Read all packed info, allocate memory and fix field structs */
167 :
168 : static my_bool _ma_read_pack_info(MARIA_SHARE *share, File file,
169 : pbool fix_keys)
170 0 : {
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 0 : DBUG_ENTER("_ma_read_pack_info");
180 :
181 0 : if (maria_quick_table_bits < 4)
182 0 : maria_quick_table_bits=4;
183 0 : else if (maria_quick_table_bits > MAX_QUICK_TABLE_BITS)
184 0 : maria_quick_table_bits=MAX_QUICK_TABLE_BITS;
185 :
186 0 : my_errno=0;
187 0 : if (my_read(file, header, sizeof(header), MYF(MY_NABP)))
188 : {
189 0 : if (!my_errno)
190 0 : 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 0 : if (memcmp(header, maria_pack_file_magic, 3))
195 : {
196 0 : my_errno=HA_ERR_WRONG_IN_RECORD;
197 0 : goto err0;
198 : }
199 0 : share->pack.version= header[3]; /* fourth uchar of magic number */
200 0 : share->pack.header_length= uint4korr(header+4);
201 0 : share->min_pack_length=(uint) uint4korr(header+8);
202 0 : share->max_pack_length=(uint) uint4korr(header+12);
203 0 : set_if_bigger(share->base.default_rec_buff_size,
204 : share->max_pack_length + 7);
205 0 : elements=uint4korr(header+16);
206 0 : intervall_length=uint4korr(header+20);
207 0 : trees=uint2korr(header+24);
208 0 : share->pack.ref_length=header[26];
209 0 : rec_reflength=header[27];
210 0 : diff_length=(int) rec_reflength - (int) share->base.rec_reflength;
211 0 : if (fix_keys)
212 0 : share->rec_reflength=rec_reflength;
213 0 : DBUG_PRINT("info", ("fixed header length: %u", HEAD_LENGTH));
214 0 : DBUG_PRINT("info", ("total header length: %lu", share->pack.header_length));
215 0 : DBUG_PRINT("info", ("pack file version: %u", share->pack.version));
216 0 : DBUG_PRINT("info", ("min pack length: %lu", share->min_pack_length));
217 0 : DBUG_PRINT("info", ("max pack length: %lu", share->max_pack_length));
218 0 : DBUG_PRINT("info", ("elements of all trees: %lu", elements));
219 0 : DBUG_PRINT("info", ("distinct values bytes: %lu", intervall_length));
220 0 : DBUG_PRINT("info", ("number of code trees: %u", trees));
221 0 : DBUG_PRINT("info", ("bytes for record lgt: %u", share->pack.ref_length));
222 0 : 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 0 : 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 0 : goto err0;
235 0 : 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 0 : length=(uint) (elements*2+trees*(1 << maria_quick_table_bits));
246 0 : 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 0 : goto err1;
252 0 : tmp_buff=share->decode_tables+length;
253 0 : disk_cache=(uchar*) (tmp_buff+OFFSET_TABLE_SIZE);
254 :
255 0 : if (my_read(file,disk_cache,
256 : (uint) (share->pack.header_length-sizeof(header)),
257 : MYF(MY_NABP)))
258 0 : goto err2;
259 : #ifdef HAVE_purify
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 0 : huff_tree_bits=max_bit(trees ? trees-1 : 0);
266 0 : init_bit_buffer(&bit_buff, disk_cache,
267 : (uint) (share->pack.header_length-sizeof(header)));
268 : /* Read new info for each field */
269 0 : for (i=0 ; i < share->base.fields ; i++)
270 : {
271 0 : share->columndef[i].base_type=(enum en_fieldtype) get_bits(&bit_buff,5);
272 0 : share->columndef[i].pack_type=(uint) get_bits(&bit_buff,6);
273 0 : share->columndef[i].space_length_bits=get_bits(&bit_buff,5);
274 0 : share->columndef[i].huff_tree=share->decode_trees+(uint) get_bits(&bit_buff,
275 : huff_tree_bits);
276 0 : share->columndef[i].unpack= get_unpack_function(share->columndef + i);
277 0 : 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 0 : 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 0 : decode_table=share->decode_tables;
288 0 : for (i=0 ; i < trees ; i++)
289 0 : if (read_huff_table(&bit_buff,share->decode_trees+i,&decode_table,
290 : &intervall_buff,tmp_buff))
291 0 : goto err3;
292 : /* Reallocate the decoding tables to the used size. */
293 0 : 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 0 : my_ptrdiff_t diff= PTR_BYTE_DIFF(decode_table,share->decode_tables);
300 0 : share->decode_tables=decode_table;
301 0 : for (i=0 ; i < trees ; i++)
302 0 : 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 0 : if (fix_keys)
308 : {
309 0 : for (i=0 ; i < share->base.keys ; i++)
310 : {
311 0 : MARIA_KEYDEF *keyinfo= &share->keyinfo[i];
312 0 : keyinfo->keylength+= (uint16) diff_length;
313 0 : keyinfo->minlength+= (uint16) diff_length;
314 0 : keyinfo->maxlength+= (uint16) diff_length;
315 0 : keyinfo->seg[keyinfo->flag & HA_FULLTEXT ?
316 : FT_SEGS : keyinfo->keysegs].length= (uint16) rec_reflength;
317 : }
318 0 : if (share->ft2_keyinfo.seg)
319 : {
320 0 : MARIA_KEYDEF *ft2_keyinfo= &share->ft2_keyinfo;
321 0 : ft2_keyinfo->keylength+= (uint16) diff_length;
322 0 : ft2_keyinfo->minlength+= (uint16) diff_length;
323 0 : ft2_keyinfo->maxlength+= (uint16) diff_length;
324 : }
325 : }
326 :
327 0 : if (bit_buff.error || bit_buff.pos < bit_buff.end)
328 : goto err3;
329 :
330 0 : DBUG_RETURN(0);
331 :
332 0 : err3:
333 0 : my_errno=HA_ERR_WRONG_IN_RECORD;
334 0 : err2:
335 0 : my_free(share->decode_tables, MYF(0));
336 0 : err1:
337 0 : my_free(share->decode_trees, MYF(0));
338 0 : err0:
339 0 : 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 : */
360 : static 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 0 : {
365 : uint min_chr,elements,char_bits,offset_bits,size,intervall_length,table_bits,
366 : next_free_offset;
367 : uint16 *ptr,*end;
368 0 : DBUG_ENTER("read_huff_table");
369 :
370 0 : if (!get_bits(bit_buff,1))
371 : {
372 : /* Byte value compression. */
373 0 : min_chr=get_bits(bit_buff,8);
374 0 : elements=get_bits(bit_buff,9);
375 0 : char_bits=get_bits(bit_buff,5);
376 0 : offset_bits=get_bits(bit_buff,5);
377 0 : intervall_length=0;
378 0 : ptr=tmp_buff;
379 0 : ptr=tmp_buff;
380 0 : DBUG_PRINT("info", ("byte value compression"));
381 0 : DBUG_PRINT("info", ("minimum uchar value: %u", min_chr));
382 0 : DBUG_PRINT("info", ("number of tree nodes: %u", elements));
383 0 : DBUG_PRINT("info", ("bits for values: %u", char_bits));
384 0 : DBUG_PRINT("info", ("bits for tree offsets: %u", offset_bits));
385 0 : if (elements > 256)
386 : {
387 0 : DBUG_PRINT("error", ("ERROR: illegal number of tree elements: %u",
388 : elements));
389 0 : DBUG_RETURN(1);
390 : }
391 : }
392 : else
393 : {
394 : /* Distinct column value compression. */
395 0 : min_chr=0;
396 0 : elements=get_bits(bit_buff,15);
397 0 : intervall_length=get_bits(bit_buff,16);
398 0 : char_bits=get_bits(bit_buff,5);
399 0 : offset_bits=get_bits(bit_buff,5);
400 0 : decode_tree->quick_table_bits=0;
401 0 : ptr= *decode_table;
402 0 : DBUG_PRINT("info", ("distinct column value compression"));
403 0 : DBUG_PRINT("info", ("number of tree nodes: %u", elements));
404 0 : DBUG_PRINT("info", ("value buffer length: %u", intervall_length));
405 0 : DBUG_PRINT("info", ("bits for value index: %u", char_bits));
406 0 : DBUG_PRINT("info", ("bits for tree offsets: %u", offset_bits));
407 : }
408 0 : size=elements*2-2;
409 0 : DBUG_PRINT("info", ("tree size in uint16: %u", size));
410 0 : DBUG_PRINT("info", ("tree size in bytes: %u",
411 : size * (uint) sizeof(uint16)));
412 :
413 0 : for (end=ptr+size ; ptr < end ; ptr++)
414 : {
415 0 : if (get_bit(bit_buff))
416 : {
417 0 : *ptr= (uint16) get_bits(bit_buff,offset_bits);
418 0 : if ((ptr + *ptr >= end) || !*ptr)
419 : {
420 0 : DBUG_PRINT("error", ("ERROR: illegal pointer in decode tree"));
421 0 : DBUG_RETURN(1);
422 : }
423 : }
424 : else
425 0 : *ptr= (uint16) (IS_CHAR + (get_bits(bit_buff,char_bits) + min_chr));
426 : }
427 0 : skip_to_next_byte(bit_buff);
428 :
429 0 : decode_tree->table= *decode_table;
430 0 : decode_tree->intervalls= *intervall_buff;
431 0 : 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 0 : table_bits= find_longest_bitstream(tmp_buff, ptr);
436 0 : if (table_bits >= OFFSET_TABLE_SIZE)
437 0 : DBUG_RETURN(1);
438 0 : if (table_bits > maria_quick_table_bits)
439 0 : table_bits=maria_quick_table_bits;
440 0 : DBUG_PRINT("info", ("table bits: %u", table_bits));
441 :
442 0 : next_free_offset= (1 << table_bits);
443 0 : make_quick_table(*decode_table,tmp_buff,&next_free_offset,0,table_bits,
444 : table_bits);
445 0 : (*decode_table)+= next_free_offset;
446 0 : decode_tree->quick_table_bits=table_bits;
447 : }
448 : else
449 : {
450 : /* Distinct column value compression. ptr started from *decode_table */
451 0 : (*decode_table)=end;
452 : /*
453 : get_bits() moves some bytes to a cache buffer in advance. May need
454 : to step back.
455 : */
456 0 : bit_buff->pos-= bit_buff->bits/8;
457 : /* Copy the distinct column values from the buffer. */
458 0 : memcpy(*intervall_buff,bit_buff->pos,(size_t) intervall_length);
459 0 : (*intervall_buff)+=intervall_length;
460 0 : bit_buff->pos+=intervall_length;
461 0 : bit_buff->bits=0;
462 : }
463 0 : 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 :
506 : static void make_quick_table(uint16 *to_table, uint16 *decode_table,
507 : uint *next_free_offset, uint value, uint bits,
508 : uint max_bits)
509 0 : {
510 0 : 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 0 : 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 0 : 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 0 : *next_free_offset=copy_decode_table(to_table, *next_free_offset,
528 : decode_table);
529 0 : DBUG_VOID_RETURN;
530 : }
531 :
532 : /* Descent on the left side. Left side bits are clear (0). */
533 0 : if (!(*decode_table & IS_CHAR))
534 : {
535 : /* Not a leaf. Follow the pointer. */
536 0 : 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 0 : 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 0 : decode_table++;
551 0 : value|= (1 << bits);
552 0 : if (!(*decode_table & IS_CHAR))
553 : {
554 : /* Not a leaf. Follow the pointer. */
555 0 : 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 0 : fill_quick_table(to_table+value,bits,max_bits,(uint) *decode_table);
566 : }
567 :
568 0 : 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 :
596 : static void fill_quick_table(uint16 *table, uint bits, uint max_bits,
597 : uint value)
598 0 : {
599 : uint16 *end;
600 0 : 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 0 : value|= (max_bits - bits) << 8 | IS_CHAR;
608 :
609 0 : for (end= table + ((my_ptrdiff_t) 1 << bits); table < end; table++)
610 : {
611 0 : *table= (uint16) value;
612 : }
613 0 : 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 :
633 : static uint copy_decode_table(uint16 *to_pos, uint offset,
634 : uint16 *decode_table)
635 0 : {
636 0 : uint prev_offset= offset;
637 0 : DBUG_ENTER("copy_decode_table");
638 :
639 : /* Descent on the left side. */
640 0 : if (!(*decode_table & IS_CHAR))
641 : {
642 : /* Set a pointer to the next target node. */
643 0 : to_pos[offset]=2;
644 : /* Copy the left hand subtree there. */
645 0 : offset=copy_decode_table(to_pos,offset+2,decode_table+ *decode_table);
646 : }
647 : else
648 : {
649 : /* Copy the uchar value. */
650 0 : to_pos[offset]= *decode_table;
651 : /* Step behind this node. */
652 0 : offset+=2;
653 : }
654 :
655 : /* Descent on the right side. */
656 0 : decode_table++;
657 0 : if (!(*decode_table & IS_CHAR))
658 : {
659 : /* Set a pointer to the next free target node. */
660 0 : to_pos[prev_offset+1]=(uint16) (offset-prev_offset-1);
661 : /* Copy the right hand subtree to the entry of that node. */
662 0 : offset=copy_decode_table(to_pos,offset,decode_table+ *decode_table);
663 : }
664 : else
665 : {
666 : /* Copy the uchar value. */
667 0 : to_pos[prev_offset+1]= *decode_table;
668 : }
669 0 : 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 :
697 : static uint find_longest_bitstream(uint16 *table, uint16 *end)
698 0 : {
699 0 : uint length=1;
700 : uint length2;
701 0 : if (!(*table & IS_CHAR))
702 : {
703 0 : uint16 *next= table + *table;
704 0 : if (next > end || next == table)
705 : {
706 0 : DBUG_PRINT("error", ("ERROR: illegal pointer in decode tree"));
707 0 : return OFFSET_TABLE_SIZE;
708 : }
709 0 : length=find_longest_bitstream(next, end)+1;
710 : }
711 0 : table++;
712 0 : if (!(*table & IS_CHAR))
713 : {
714 0 : uint16 *next= table + *table;
715 0 : if (next > end || next == table)
716 : {
717 0 : DBUG_PRINT("error", ("ERROR: illegal pointer in decode tree"));
718 0 : return OFFSET_TABLE_SIZE;
719 : }
720 0 : length2= find_longest_bitstream(next, end) + 1;
721 0 : length=max(length,length2);
722 : }
723 0 : 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 :
741 : int _ma_read_pack_record(MARIA_HA *info, uchar *buf, MARIA_RECORD_POS filepos)
742 0 : {
743 : MARIA_BLOCK_INFO block_info;
744 : File file;
745 0 : DBUG_ENTER("maria_read_pack_record");
746 :
747 0 : if (filepos == HA_OFFSET_ERROR)
748 0 : DBUG_RETURN(my_errno); /* _search() didn't find record */
749 :
750 0 : file= info->dfile.file;
751 0 : if (_ma_pack_get_block_info(info, &info->bit_buff, &block_info,
752 : &info->rec_buff, &info->rec_buff_size, file,
753 : filepos))
754 0 : goto err;
755 0 : if (my_read(file, info->rec_buff + block_info.offset ,
756 : block_info.rec_len - block_info.offset, MYF(MY_NABP)))
757 0 : goto panic;
758 0 : info->update|= HA_STATE_AKTIV;
759 0 : DBUG_RETURN(_ma_pack_rec_unpack(info,&info->bit_buff, buf,
760 : info->rec_buff, block_info.rec_len));
761 0 : panic:
762 0 : my_errno=HA_ERR_WRONG_IN_RECORD;
763 0 : err:
764 0 : DBUG_RETURN(my_errno);
765 : }
766 :
767 :
768 :
769 : int _ma_pack_rec_unpack(register MARIA_HA *info, MARIA_BIT_BUFF *bit_buff,
770 : register uchar *to, uchar *from, ulong reclength)
771 0 : {
772 : uchar *end_field;
773 : reg3 MARIA_COLUMNDEF *end;
774 : MARIA_COLUMNDEF *current_field;
775 0 : MARIA_SHARE *share= info->s;
776 0 : DBUG_ENTER("_ma_pack_rec_unpack");
777 :
778 0 : if (info->s->base.null_bytes)
779 : {
780 0 : memcpy(to, from, info->s->base.null_bytes);
781 0 : to+= info->s->base.null_bytes;
782 0 : from+= info->s->base.null_bytes;
783 0 : reclength-= info->s->base.null_bytes;
784 : }
785 0 : init_bit_buffer(bit_buff, from, reclength);
786 0 : for (current_field=share->columndef, end=current_field+share->base.fields ;
787 0 : current_field < end ;
788 0 : current_field++,to=end_field)
789 : {
790 0 : end_field=to+current_field->length;
791 0 : (*current_field->unpack)(current_field, bit_buff, to, end_field);
792 : }
793 0 : if (!bit_buff->error &&
794 : bit_buff->pos - bit_buff->bits / 8 == bit_buff->end)
795 0 : DBUG_RETURN(0);
796 0 : info->update&= ~HA_STATE_AKTIV;
797 0 : DBUG_RETURN(my_errno=HA_ERR_WRONG_IN_RECORD);
798 : } /* _ma_pack_rec_unpack */
799 :
800 :
801 : /* Return function to unpack field */
802 :
803 : static void (*get_unpack_function(MARIA_COLUMNDEF *rec))
804 : (MARIA_COLUMNDEF *, MARIA_BIT_BUFF *, uchar *, uchar *)
805 0 : {
806 0 : switch (rec->base_type) {
807 : case FIELD_SKIP_ZERO:
808 0 : if (rec->pack_type & PACK_TYPE_ZERO_FILL)
809 0 : return &uf_zerofill_skip_zero;
810 0 : return &uf_skip_zero;
811 : case FIELD_NORMAL:
812 0 : if (rec->pack_type & PACK_TYPE_SPACE_FIELDS)
813 0 : return &uf_space_normal;
814 0 : if (rec->pack_type & PACK_TYPE_ZERO_FILL)
815 0 : return &uf_zerofill_normal;
816 0 : return &decode_bytes;
817 : case FIELD_SKIP_ENDSPACE:
818 0 : if (rec->pack_type & PACK_TYPE_SPACE_FIELDS)
819 : {
820 0 : if (rec->pack_type & PACK_TYPE_SELECTED)
821 0 : return &uf_space_endspace_selected;
822 0 : return &uf_space_endspace;
823 : }
824 0 : if (rec->pack_type & PACK_TYPE_SELECTED)
825 0 : return &uf_endspace_selected;
826 0 : return &uf_endspace;
827 : case FIELD_SKIP_PRESPACE:
828 0 : if (rec->pack_type & PACK_TYPE_SPACE_FIELDS)
829 : {
830 0 : if (rec->pack_type & PACK_TYPE_SELECTED)
831 0 : return &uf_space_prespace_selected;
832 0 : return &uf_space_prespace;
833 : }
834 0 : if (rec->pack_type & PACK_TYPE_SELECTED)
835 0 : return &uf_prespace_selected;
836 0 : return &uf_prespace;
837 : case FIELD_CONSTANT:
838 0 : return &uf_constant;
839 : case FIELD_INTERVALL:
840 0 : return &uf_intervall;
841 : case FIELD_ZERO:
842 : case FIELD_CHECK:
843 0 : return &uf_zero;
844 : case FIELD_BLOB:
845 0 : return &uf_blob;
846 : case FIELD_VARCHAR:
847 0 : if (rec->length <= 256) /* 255 + 1 uchar length */
848 0 : return &uf_varchar1;
849 0 : return &uf_varchar2;
850 : case FIELD_LAST:
851 : default:
852 0 : return 0; /* This should never happend */
853 : }
854 : }
855 :
856 : /* The different functions to unpack a field */
857 :
858 : static void uf_zerofill_skip_zero(MARIA_COLUMNDEF *rec,
859 : MARIA_BIT_BUFF *bit_buff,
860 : uchar *to, uchar *end)
861 0 : {
862 0 : if (get_bit(bit_buff))
863 0 : bzero((char*) to,(uint) (end-to));
864 : else
865 : {
866 0 : end-=rec->space_length_bits;
867 0 : decode_bytes(rec,bit_buff,to,end);
868 0 : bzero((char*) end,rec->space_length_bits);
869 : }
870 : }
871 :
872 : static void uf_skip_zero(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
873 : uchar *to, uchar *end)
874 0 : {
875 0 : if (get_bit(bit_buff))
876 0 : bzero((char*) to,(uint) (end-to));
877 : else
878 0 : decode_bytes(rec,bit_buff,to,end);
879 : }
880 :
881 : static void uf_space_normal(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
882 : uchar *to, uchar *end)
883 0 : {
884 0 : if (get_bit(bit_buff))
885 0 : bfill(to, (end-to), ' ');
886 : else
887 0 : decode_bytes(rec,bit_buff,to,end);
888 : }
889 :
890 : static void uf_space_endspace_selected(MARIA_COLUMNDEF *rec,
891 : MARIA_BIT_BUFF *bit_buff,
892 : uchar *to, uchar *end)
893 0 : {
894 : uint spaces;
895 0 : if (get_bit(bit_buff))
896 0 : bfill(to, (end-to), ' ');
897 : else
898 : {
899 0 : if (get_bit(bit_buff))
900 : {
901 0 : if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
902 : {
903 0 : bit_buff->error=1;
904 0 : return;
905 : }
906 0 : if (to+spaces != end)
907 0 : decode_bytes(rec,bit_buff,to,end-spaces);
908 0 : bfill(end - spaces, spaces, ' ');
909 : }
910 : else
911 0 : decode_bytes(rec,bit_buff,to,end);
912 : }
913 : }
914 :
915 : static void uf_endspace_selected(MARIA_COLUMNDEF *rec,
916 : MARIA_BIT_BUFF *bit_buff,
917 : uchar *to, uchar *end)
918 0 : {
919 : uint spaces;
920 0 : if (get_bit(bit_buff))
921 : {
922 0 : if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
923 : {
924 0 : bit_buff->error=1;
925 0 : return;
926 : }
927 0 : if (to+spaces != end)
928 0 : decode_bytes(rec,bit_buff,to,end-spaces);
929 0 : bfill(end - spaces, spaces, ' ');
930 : }
931 : else
932 0 : decode_bytes(rec,bit_buff,to,end);
933 : }
934 :
935 : static void uf_space_endspace(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
936 : uchar *to, uchar *end)
937 0 : {
938 : uint spaces;
939 0 : if (get_bit(bit_buff))
940 0 : bfill(to, (end-to), ' ');
941 : else
942 : {
943 0 : if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
944 : {
945 0 : bit_buff->error=1;
946 0 : return;
947 : }
948 0 : if (to+spaces != end)
949 0 : decode_bytes(rec,bit_buff,to,end-spaces);
950 0 : bfill(end - spaces, spaces, ' ');
951 : }
952 : }
953 :
954 : static void uf_endspace(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
955 : uchar *to, uchar *end)
956 0 : {
957 : uint spaces;
958 0 : if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
959 : {
960 0 : bit_buff->error=1;
961 0 : return;
962 : }
963 0 : if (to+spaces != end)
964 0 : decode_bytes(rec,bit_buff,to,end-spaces);
965 0 : bfill(end - spaces, spaces, ' ');
966 : }
967 :
968 : static void uf_space_prespace_selected(MARIA_COLUMNDEF *rec,
969 : MARIA_BIT_BUFF *bit_buff,
970 : uchar *to, uchar *end)
971 0 : {
972 : uint spaces;
973 0 : if (get_bit(bit_buff))
974 0 : bfill(to, (end-to), ' ');
975 : else
976 : {
977 0 : if (get_bit(bit_buff))
978 : {
979 0 : if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
980 : {
981 0 : bit_buff->error=1;
982 0 : return;
983 : }
984 0 : bfill(to, spaces, ' ');
985 0 : if (to+spaces != end)
986 0 : decode_bytes(rec,bit_buff,to+spaces,end);
987 : }
988 : else
989 0 : decode_bytes(rec,bit_buff,to,end);
990 : }
991 : }
992 :
993 :
994 : static void uf_prespace_selected(MARIA_COLUMNDEF *rec,
995 : MARIA_BIT_BUFF *bit_buff,
996 : uchar *to, uchar *end)
997 0 : {
998 : uint spaces;
999 0 : if (get_bit(bit_buff))
1000 : {
1001 0 : if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
1002 : {
1003 0 : bit_buff->error=1;
1004 0 : return;
1005 : }
1006 0 : bfill(to, spaces, ' ');
1007 0 : if (to+spaces != end)
1008 0 : decode_bytes(rec,bit_buff,to+spaces,end);
1009 : }
1010 : else
1011 0 : decode_bytes(rec,bit_buff,to,end);
1012 : }
1013 :
1014 :
1015 : static void uf_space_prespace(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
1016 : uchar *to, uchar *end)
1017 0 : {
1018 : uint spaces;
1019 0 : if (get_bit(bit_buff))
1020 0 : bfill(to, (end-to), ' ');
1021 : else
1022 : {
1023 0 : if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
1024 : {
1025 0 : bit_buff->error=1;
1026 0 : return;
1027 : }
1028 0 : bfill(to, spaces, ' ');
1029 0 : if (to+spaces != end)
1030 0 : decode_bytes(rec,bit_buff,to+spaces,end);
1031 : }
1032 : }
1033 :
1034 : static void uf_prespace(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
1035 : uchar *to, uchar *end)
1036 0 : {
1037 : uint spaces;
1038 0 : if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
1039 : {
1040 0 : bit_buff->error=1;
1041 0 : return;
1042 : }
1043 0 : bfill(to, spaces, ' ');
1044 0 : if (to+spaces != end)
1045 0 : decode_bytes(rec,bit_buff,to+spaces,end);
1046 : }
1047 :
1048 : static void uf_zerofill_normal(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
1049 : uchar *to, uchar *end)
1050 0 : {
1051 0 : end-=rec->space_length_bits;
1052 0 : decode_bytes(rec,bit_buff, to, end);
1053 0 : bzero((char*) end,rec->space_length_bits);
1054 : }
1055 :
1056 : static void uf_constant(MARIA_COLUMNDEF *rec,
1057 : MARIA_BIT_BUFF *bit_buff __attribute__((unused)),
1058 : uchar *to, uchar *end)
1059 0 : {
1060 0 : memcpy(to,rec->huff_tree->intervalls,(size_t) (end-to));
1061 : }
1062 :
1063 : static void uf_intervall(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
1064 : uchar *to,
1065 : uchar *end)
1066 0 : {
1067 0 : reg1 uint field_length=(uint) (end-to);
1068 0 : memcpy(to,rec->huff_tree->intervalls+field_length*decode_pos(bit_buff,
1069 : rec->huff_tree),
1070 : (size_t) field_length);
1071 : }
1072 :
1073 :
1074 : /*ARGSUSED*/
1075 : static void uf_zero(MARIA_COLUMNDEF *rec __attribute__((unused)),
1076 : MARIA_BIT_BUFF *bit_buff __attribute__((unused)),
1077 : uchar *to, uchar *end)
1078 0 : {
1079 0 : bzero(to, (uint) (end-to));
1080 : }
1081 :
1082 : static void uf_blob(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
1083 : uchar *to, uchar *end)
1084 0 : {
1085 0 : if (get_bit(bit_buff))
1086 0 : bzero(to, (uint) (end-to));
1087 : else
1088 : {
1089 0 : ulong length=get_bits(bit_buff,rec->space_length_bits);
1090 0 : uint pack_length=(uint) (end-to)-portable_sizeof_char_ptr;
1091 0 : if (bit_buff->blob_pos+length > bit_buff->blob_end)
1092 : {
1093 0 : bit_buff->error=1;
1094 0 : bzero(to, (end-to));
1095 0 : return;
1096 : }
1097 0 : decode_bytes(rec, bit_buff, bit_buff->blob_pos,
1098 : bit_buff->blob_pos + length);
1099 0 : _ma_store_blob_length(to, pack_length, length);
1100 0 : memcpy_fixed((uchar*) to+pack_length,(uchar*) &bit_buff->blob_pos,
1101 : sizeof(uchar*));
1102 0 : bit_buff->blob_pos+=length;
1103 : }
1104 : }
1105 :
1106 :
1107 : static void uf_varchar1(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
1108 : uchar *to, uchar *end __attribute__((unused)))
1109 0 : {
1110 0 : if (get_bit(bit_buff))
1111 0 : to[0]= 0; /* Zero lengths */
1112 : else
1113 : {
1114 0 : ulong length=get_bits(bit_buff,rec->space_length_bits);
1115 0 : *to= (char) length;
1116 0 : decode_bytes(rec,bit_buff,to+1,to+1+length);
1117 : }
1118 : }
1119 :
1120 :
1121 : static void uf_varchar2(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
1122 : uchar *to, uchar *end __attribute__((unused)))
1123 0 : {
1124 0 : if (get_bit(bit_buff))
1125 0 : to[0]=to[1]=0; /* Zero lengths */
1126 : else
1127 : {
1128 0 : ulong length=get_bits(bit_buff,rec->space_length_bits);
1129 0 : int2store(to,length);
1130 0 : 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 :
1138 : static 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 wich 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 :
1231 : static void decode_bytes(MARIA_COLUMNDEF *rec, MARIA_BIT_BUFF *bit_buff,
1232 : uchar *to, uchar *end)
1233 0 : {
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 0 : decode_tree=rec->huff_tree;
1240 0 : bits=bit_buff->bits; /* Save in reg for quicker access */
1241 0 : table_bits=decode_tree->quick_table_bits;
1242 0 : table_and= (1 << table_bits)-1;
1243 :
1244 : do
1245 : {
1246 0 : if (bits < table_bits)
1247 : {
1248 0 : if (bit_buff->pos > bit_buff->end+1)
1249 : {
1250 0 : bit_buff->error=1;
1251 0 : return; /* Can't be right */
1252 : }
1253 : #if BITS_SAVED == 32
1254 0 : 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 0 : bit_buff->pos+=3;
1259 0 : 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 0 : low_byte=(bit_buff->current_byte >> (bits - table_bits)) & table_and;
1279 0 : low_byte=decode_tree->table[low_byte];
1280 0 : if (low_byte & IS_CHAR)
1281 : {
1282 0 : *to++ = (low_byte & 255); /* Found char in quick table */
1283 0 : bits-= ((low_byte >> 8) & 31); /* Remove bits used */
1284 : }
1285 : else
1286 : { /* Map through rest of decode-table */
1287 0 : pos=decode_tree->table+low_byte;
1288 0 : bits-=table_bits;
1289 : for (;;)
1290 : {
1291 0 : if (bits < 8)
1292 : { /* We don't need to check end */
1293 : #if BITS_SAVED == 32
1294 0 : 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 0 : bit_buff->pos+=3;
1299 0 : 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 0 : low_byte=(uint) (bit_buff->current_byte >> (bits-8));
1308 0 : decode_bytes_test_bit(0);
1309 0 : decode_bytes_test_bit(1);
1310 0 : decode_bytes_test_bit(2);
1311 0 : decode_bytes_test_bit(3);
1312 0 : decode_bytes_test_bit(4);
1313 0 : decode_bytes_test_bit(5);
1314 0 : decode_bytes_test_bit(6);
1315 0 : decode_bytes_test_bit(7);
1316 0 : bits-=8;
1317 0 : }
1318 0 : *to++ = (char) *pos;
1319 : }
1320 0 : } while (to != end);
1321 :
1322 0 : bit_buff->bits=bits;
1323 : return;
1324 : }
1325 : #endif /* BIT_SAVED == 64 */
1326 :
1327 :
1328 : static uint decode_pos(MARIA_BIT_BUFF *bit_buff,
1329 : MARIA_DECODE_TREE *decode_tree)
1330 0 : {
1331 0 : uint16 *pos=decode_tree->table;
1332 : for (;;)
1333 : {
1334 0 : if (get_bit(bit_buff))
1335 0 : pos++;
1336 0 : if (*pos & IS_CHAR)
1337 0 : return (uint) (*pos & ~IS_CHAR);
1338 0 : pos+= *pos;
1339 0 : }
1340 : }
1341 :
1342 :
1343 : int _ma_read_rnd_pack_record(MARIA_HA *info,
1344 : uchar *buf,
1345 : register MARIA_RECORD_POS filepos,
1346 : my_bool skip_deleted_blocks)
1347 0 : {
1348 : File file;
1349 : MARIA_BLOCK_INFO block_info;
1350 0 : MARIA_SHARE *share= info->s;
1351 0 : DBUG_ENTER("_ma_read_rnd_pack_record");
1352 :
1353 0 : if (filepos >= info->state->data_file_length)
1354 : {
1355 0 : my_errno= HA_ERR_END_OF_FILE;
1356 0 : goto err;
1357 : }
1358 :
1359 0 : file= info->dfile.file;
1360 0 : if (info->opt_flag & READ_CACHE_USED)
1361 : {
1362 0 : if (_ma_read_cache(&info->rec_cache, block_info.header,
1363 : filepos, share->pack.ref_length,
1364 : skip_deleted_blocks ? READING_NEXT : 0))
1365 0 : goto err;
1366 0 : file= -1;
1367 : }
1368 0 : if (_ma_pack_get_block_info(info, &info->bit_buff, &block_info,
1369 : &info->rec_buff, &info->rec_buff_size,
1370 : file, filepos))
1371 0 : goto err; /* Error code is already set */
1372 : #ifndef DBUG_OFF
1373 0 : if (block_info.rec_len > share->max_pack_length)
1374 : {
1375 0 : my_errno=HA_ERR_WRONG_IN_RECORD;
1376 0 : goto err;
1377 : }
1378 : #endif
1379 :
1380 0 : if (info->opt_flag & READ_CACHE_USED)
1381 : {
1382 0 : if (_ma_read_cache(&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 0 : if (my_read(info->dfile.file, info->rec_buff + block_info.offset,
1390 : block_info.rec_len-block_info.offset,
1391 : MYF(MY_NABP)))
1392 0 : goto err;
1393 : }
1394 0 : info->packed_length= block_info.rec_len;
1395 0 : info->cur_row.lastpos= filepos;
1396 0 : info->cur_row.nextpos= block_info.filepos+block_info.rec_len;
1397 0 : info->update|= HA_STATE_AKTIV | HA_STATE_KEY_CHANGED;
1398 :
1399 0 : DBUG_RETURN (_ma_pack_rec_unpack(info, &info->bit_buff, buf,
1400 : info->rec_buff, block_info.rec_len));
1401 0 : err:
1402 0 : DBUG_RETURN(my_errno);
1403 : }
1404 :
1405 :
1406 : /* Read and process header from a huff-record-file */
1407 :
1408 : uint _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 0 : {
1413 0 : uchar *header= info->header;
1414 : uint head_length,ref_length;
1415 0 : LINT_INIT(ref_length);
1416 :
1417 0 : if (file >= 0)
1418 : {
1419 0 : 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 0 : VOID(my_seek(file,filepos,MY_SEEK_SET,MYF(0)));
1425 0 : if (my_read(file, header,ref_length,MYF(MY_NABP)))
1426 0 : return BLOCK_FATAL_ERROR;
1427 0 : DBUG_DUMP("header", header, ref_length);
1428 : }
1429 0 : head_length= read_pack_length((uint) maria->s->pack.version, header,
1430 : &info->rec_len);
1431 0 : if (maria->s->base.blobs)
1432 : {
1433 0 : 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 0 : 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 0 : return BLOCK_FATAL_ERROR; /* not enough memory */
1444 0 : bit_buff->blob_pos= *rec_buff_p + info->rec_len;
1445 0 : bit_buff->blob_end= bit_buff->blob_pos + info->blob_len;
1446 0 : maria->blob_length=info->blob_len;
1447 : }
1448 0 : info->filepos=filepos+head_length;
1449 0 : if (file > 0)
1450 : {
1451 0 : info->offset=min(info->rec_len, ref_length - head_length);
1452 0 : memcpy(*rec_buff_p, header + head_length, info->offset);
1453 : }
1454 0 : return 0;
1455 : }
1456 :
1457 :
1458 : /* rutines for bit buffer */
1459 : /* Note buffer must be 6 uchar bigger than longest row */
1460 :
1461 : static void init_bit_buffer(MARIA_BIT_BUFF *bit_buff, uchar *buffer,
1462 : uint length)
1463 0 : {
1464 0 : bit_buff->pos=buffer;
1465 0 : bit_buff->end=buffer+length;
1466 0 : bit_buff->bits=bit_buff->error=0;
1467 0 : bit_buff->current_byte=0; /* Avoid purify errors */
1468 : }
1469 :
1470 : static uint fill_and_get_bits(MARIA_BIT_BUFF *bit_buff, uint count)
1471 0 : {
1472 : uint tmp;
1473 0 : count-=bit_buff->bits;
1474 0 : tmp=(bit_buff->current_byte & mask[bit_buff->bits]) << count;
1475 0 : fill_buffer(bit_buff);
1476 0 : bit_buff->bits=BITS_SAVED - count;
1477 0 : 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 :
1483 : static void fill_buffer(MARIA_BIT_BUFF *bit_buff)
1484 0 : {
1485 0 : if (bit_buff->pos >= bit_buff->end)
1486 : {
1487 0 : bit_buff->error= 1;
1488 0 : bit_buff->current_byte=0;
1489 0 : 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 0 : 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 0 : 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 :
1519 : static uint max_bit(register uint value)
1520 0 : {
1521 0 : reg2 uint power=1;
1522 :
1523 0 : while ((value>>=1))
1524 0 : power++;
1525 0 : return (power);
1526 : }
1527 :
1528 :
1529 : /*****************************************************************************
1530 : Some redefined functions to handle files when we are using memmap
1531 : *****************************************************************************/
1532 : #ifdef HAVE_SYS_MMAN_H
1533 : #include <sys/mman.h>
1534 : #endif
1535 :
1536 : #ifdef HAVE_MMAP
1537 :
1538 : static int _ma_read_mempack_record(MARIA_HA *info, uchar *buf,
1539 : MARIA_RECORD_POS filepos);
1540 : static int _ma_read_rnd_mempack_record(MARIA_HA*, uchar *, MARIA_RECORD_POS,
1541 : my_bool);
1542 :
1543 : my_bool _ma_memmap_file(MARIA_HA *info)
1544 0 : {
1545 0 : MARIA_SHARE *share= info->s;
1546 0 : DBUG_ENTER("maria_memmap_file");
1547 :
1548 0 : if (!info->s->file_map)
1549 : {
1550 0 : if (my_seek(info->dfile.file, 0L, MY_SEEK_END, MYF(0)) <
1551 : share->state.state.data_file_length+MEMMAP_EXTRA_MARGIN)
1552 : {
1553 0 : DBUG_PRINT("warning",("File isn't extended for memmap"));
1554 0 : DBUG_RETURN(0);
1555 : }
1556 0 : if (_ma_dynmap_file(info, share->state.state.data_file_length))
1557 0 : DBUG_RETURN(0);
1558 : }
1559 0 : info->opt_flag|= MEMMAP_USED;
1560 0 : info->read_record= share->read_record= _ma_read_mempack_record;
1561 0 : share->scan= _ma_read_rnd_mempack_record;
1562 0 : DBUG_RETURN(1);
1563 : }
1564 :
1565 :
1566 : void _ma_unmap_file(MARIA_HA *info)
1567 0 : {
1568 0 : VOID(my_munmap((char*) info->s->file_map,
1569 : (size_t) info->s->mmaped_length + MEMMAP_EXTRA_MARGIN));
1570 : }
1571 :
1572 :
1573 : static uchar *
1574 : _ma_mempack_get_block_info(MARIA_HA *maria,
1575 : MARIA_BIT_BUFF *bit_buff,
1576 : MARIA_BLOCK_INFO *info,
1577 : uchar **rec_buff_p,
1578 : size_t *rec_buff_size_p,
1579 : uchar *header)
1580 0 : {
1581 0 : header+= read_pack_length((uint) maria->s->pack.version, header,
1582 : &info->rec_len);
1583 0 : if (maria->s->base.blobs)
1584 : {
1585 0 : header+= read_pack_length((uint) maria->s->pack.version, header,
1586 : &info->blob_len);
1587 : /* _ma_alloc_rec_buff sets my_errno on error */
1588 0 : if (_ma_alloc_buffer(rec_buff_p, rec_buff_size_p,
1589 : info->blob_len + maria->s->base.extra_rec_buff_size))
1590 0 : return 0; /* not enough memory */
1591 0 : bit_buff->blob_pos= *rec_buff_p;
1592 0 : bit_buff->blob_end= *rec_buff_p + info->blob_len;
1593 : }
1594 0 : return header;
1595 : }
1596 :
1597 :
1598 : static int _ma_read_mempack_record(MARIA_HA *info, uchar *buf,
1599 : MARIA_RECORD_POS filepos)
1600 0 : {
1601 : MARIA_BLOCK_INFO block_info;
1602 0 : MARIA_SHARE *share= info->s;
1603 : uchar *pos;
1604 0 : DBUG_ENTER("maria_read_mempack_record");
1605 :
1606 0 : if (filepos == HA_OFFSET_ERROR)
1607 0 : DBUG_RETURN(my_errno); /* _search() didn't find record */
1608 :
1609 0 : if (!(pos= (uchar*) _ma_mempack_get_block_info(info, &info->bit_buff,
1610 : &block_info, &info->rec_buff,
1611 : &info->rec_buff_size,
1612 : (uchar*) share->file_map+
1613 : filepos)))
1614 0 : DBUG_RETURN(my_errno);
1615 0 : DBUG_RETURN(_ma_pack_rec_unpack(info, &info->bit_buff, buf,
1616 : pos, block_info.rec_len));
1617 : }
1618 :
1619 :
1620 : /*ARGSUSED*/
1621 : static int _ma_read_rnd_mempack_record(MARIA_HA *info,
1622 : uchar *buf,
1623 : register MARIA_RECORD_POS filepos,
1624 : my_bool skip_deleted_blocks
1625 : __attribute__((unused)))
1626 0 : {
1627 : MARIA_BLOCK_INFO block_info;
1628 0 : MARIA_SHARE *share= info->s;
1629 : uchar *pos,*start;
1630 0 : DBUG_ENTER("_ma_read_rnd_mempack_record");
1631 :
1632 0 : if (filepos >= share->state.state.data_file_length)
1633 : {
1634 0 : my_errno=HA_ERR_END_OF_FILE;
1635 0 : goto err;
1636 : }
1637 0 : if (!(pos= (uchar*) _ma_mempack_get_block_info(info, &info->bit_buff,
1638 : &block_info,
1639 : &info->rec_buff,
1640 : &info->rec_buff_size,
1641 : (uchar*)
1642 : (start= share->file_map +
1643 : filepos))))
1644 0 : goto err;
1645 : #ifndef DBUG_OFF
1646 0 : if (block_info.rec_len > info->s->max_pack_length)
1647 : {
1648 0 : my_errno=HA_ERR_WRONG_IN_RECORD;
1649 0 : goto err;
1650 : }
1651 : #endif
1652 0 : info->packed_length=block_info.rec_len;
1653 0 : info->cur_row.lastpos= filepos;
1654 0 : info->cur_row.nextpos= filepos+(uint) (pos-start)+block_info.rec_len;
1655 0 : info->update|= HA_STATE_AKTIV | HA_STATE_KEY_CHANGED;
1656 :
1657 0 : DBUG_RETURN (_ma_pack_rec_unpack(info, &info->bit_buff, buf,
1658 : pos, block_info.rec_len));
1659 0 : err:
1660 0 : DBUG_RETURN(my_errno);
1661 : }
1662 :
1663 : #endif /* HAVE_MMAP */
1664 :
1665 : /* Save length of row */
1666 :
1667 : uint _ma_save_pack_length(uint version, uchar *block_buff, ulong length)
1668 0 : {
1669 0 : if (length < 254)
1670 : {
1671 0 : *(uchar*) block_buff= (uchar) length;
1672 0 : return 1;
1673 : }
1674 0 : if (length <= 65535)
1675 : {
1676 0 : *(uchar*) block_buff=254;
1677 0 : int2store(block_buff+1,(uint) length);
1678 0 : return 3;
1679 : }
1680 0 : *(uchar*) block_buff=255;
1681 0 : if (version == 1) /* old format */
1682 : {
1683 0 : DBUG_ASSERT(length <= 0xFFFFFF);
1684 0 : int3store(block_buff + 1, (ulong) length);
1685 0 : return 4;
1686 : }
1687 : else
1688 : {
1689 0 : int4store(block_buff + 1, (ulong) length);
1690 0 : return 5;
1691 : }
1692 : }
1693 :
1694 :
1695 : static uint read_pack_length(uint version, const uchar *buf, ulong *length)
1696 0 : {
1697 0 : if (buf[0] < 254)
1698 : {
1699 0 : *length= buf[0];
1700 0 : return 1;
1701 : }
1702 0 : else if (buf[0] == 254)
1703 : {
1704 0 : *length= uint2korr(buf + 1);
1705 0 : return 3;
1706 : }
1707 0 : if (version == 1) /* old format */
1708 : {
1709 0 : *length= uint3korr(buf + 1);
1710 0 : return 4;
1711 : }
1712 : else
1713 : {
1714 0 : *length= uint4korr(buf + 1);
1715 0 : return 5;
1716 : }
1717 : }
1718 :
1719 :
1720 : uint _ma_calc_pack_length(uint version, ulong length)
1721 0 : {
1722 0 : return (length < 254) ? 1 : (length < 65536) ? 3 : (version == 1) ? 4 : 5;
1723 : }
|