1
/* Copyright (C) 2000-2006 MySQL AB
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.
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.
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 */
16
/* Functions to compressed records */
18
#include "myisamdef.h"
20
#define IS_CHAR ((uint) 32768) /* Bit if char (not offset) in tree */
22
/* Some definitions to keep in sync with myisampack.c */
23
#define HEAD_LENGTH 32 /* Length of fixed header */
27
#define MAX_QUICK_TABLE_BITS 9 /* Because we may shift in 24 bits */
30
#define MAX_QUICK_TABLE_BITS 6
33
#define get_bit(BU) ((BU)->bits ? \
34
(BU)->current_byte & ((mi_bit_type) 1 << --(BU)->bits) :\
35
(fill_buffer(BU), (BU)->bits= BITS_SAVED-1,\
36
(BU)->current_byte & ((mi_bit_type) 1 << (BITS_SAVED-1))))
37
#define skip_to_next_byte(BU) ((BU)->bits&=~7)
38
#define get_bits(BU,count) (((BU)->bits >= count) ? (((BU)->current_byte >> ((BU)->bits-=count)) & mask[count]) : fill_and_get_bits(BU,count))
40
#define decode_bytes_test_bit(bit) \
41
if (low_byte & (1 << (7-bit))) \
44
{ bits-=(bit+1); break; } \
47
/* Size in uint16 of a Huffman tree for byte compression of 256 byte values. */
48
#define OFFSET_TABLE_SIZE 512
50
static uint read_huff_table(MI_BIT_BUFF *bit_buff,MI_DECODE_TREE *decode_tree,
51
uint16 **decode_table,uchar **intervall_buff,
53
static void make_quick_table(uint16 *to_table,uint16 *decode_table,
54
uint *next_free,uint value,uint bits,
56
static void fill_quick_table(uint16 *table,uint bits, uint max_bits,
58
static uint copy_decode_table(uint16 *to_pos,uint offset,
59
uint16 *decode_table);
60
static uint find_longest_bitstream(uint16 *table, uint16 *end);
61
static void (*get_unpack_function(MI_COLUMNDEF *rec))(MI_COLUMNDEF *field,
65
static void uf_zerofill_skip_zero(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
66
uchar *to,uchar *end);
67
static void uf_skip_zero(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
68
uchar *to,uchar *end);
69
static void uf_space_normal(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
70
uchar *to,uchar *end);
71
static void uf_space_endspace_selected(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
72
uchar *to, uchar *end);
73
static void uf_endspace_selected(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
74
uchar *to,uchar *end);
75
static void uf_space_endspace(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
76
uchar *to,uchar *end);
77
static void uf_endspace(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
78
uchar *to,uchar *end);
79
static void uf_space_prespace_selected(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
80
uchar *to, uchar *end);
81
static void uf_prespace_selected(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
82
uchar *to,uchar *end);
83
static void uf_space_prespace(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
84
uchar *to,uchar *end);
85
static void uf_prespace(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
86
uchar *to,uchar *end);
87
static void uf_zerofill_normal(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
88
uchar *to,uchar *end);
89
static void uf_constant(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
90
uchar *to,uchar *end);
91
static void uf_intervall(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
92
uchar *to,uchar *end);
93
static void uf_zero(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
94
uchar *to,uchar *end);
95
static void uf_blob(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
96
uchar *to, uchar *end);
97
static void uf_varchar1(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
98
uchar *to, uchar *end);
99
static void uf_varchar2(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
100
uchar *to, uchar *end);
101
static void decode_bytes(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
102
uchar *to,uchar *end);
103
static uint decode_pos(MI_BIT_BUFF *bit_buff,MI_DECODE_TREE *decode_tree);
104
static void init_bit_buffer(MI_BIT_BUFF *bit_buff,uchar *buffer,uint length);
105
static uint fill_and_get_bits(MI_BIT_BUFF *bit_buff,uint count);
106
static void fill_buffer(MI_BIT_BUFF *bit_buff);
107
static uint max_bit(uint value);
109
static uchar *_mi_mempack_get_block_info(MI_INFO *myisam, MI_BIT_BUFF *bit_buff,
110
MI_BLOCK_INFO *info, uchar **rec_buff_p,
114
static mi_bit_type mask[]=
117
0x00000001, 0x00000003, 0x00000007, 0x0000000f,
118
0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff,
119
0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff,
120
0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff,
122
0x0001ffff, 0x0003ffff, 0x0007ffff, 0x000fffff,
123
0x001fffff, 0x003fffff, 0x007fffff, 0x00ffffff,
124
0x01ffffff, 0x03ffffff, 0x07ffffff, 0x0fffffff,
125
0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff,
130
/* Read all packed info, allocate memory and fix field structs */
132
my_bool _mi_read_pack_info(MI_INFO *info, bool fix_keys)
136
uint i,trees,huff_tree_bits,rec_reflength,length;
137
uint16 *decode_table,*tmp_buff;
138
ulong elements,intervall_length;
140
uchar *intervall_buff;
141
uchar header[HEAD_LENGTH];
142
MYISAM_SHARE *share=info->s;
143
MI_BIT_BUFF bit_buff;
145
if (myisam_quick_table_bits < 4)
146
myisam_quick_table_bits=4;
147
else if (myisam_quick_table_bits > MAX_QUICK_TABLE_BITS)
148
myisam_quick_table_bits=MAX_QUICK_TABLE_BITS;
152
if (my_read(file,(uchar*) header,sizeof(header),MYF(MY_NABP)))
155
my_errno=HA_ERR_END_OF_FILE;
158
/* Only the first three bytes of magic number are independent of version. */
159
if (memcmp((uchar*) header, (uchar*) myisam_pack_file_magic, 3))
161
my_errno=HA_ERR_WRONG_IN_RECORD;
164
share->pack.version= header[3]; /* fourth byte of magic number */
165
share->pack.header_length= uint4korr(header+4);
166
share->min_pack_length=(uint) uint4korr(header+8);
167
share->max_pack_length=(uint) uint4korr(header+12);
168
elements=uint4korr(header+16);
169
intervall_length=uint4korr(header+20);
170
trees=uint2korr(header+24);
171
share->pack.ref_length=header[26];
172
rec_reflength=header[27];
173
diff_length=(int) rec_reflength - (int) share->base.rec_reflength;
175
share->rec_reflength=rec_reflength;
176
share->base.min_block_length=share->min_pack_length+1;
177
if (share->min_pack_length > 254)
178
share->base.min_block_length+=2;
183
- Distinct column values
185
if (!(share->decode_trees=(MI_DECODE_TREE*)
186
my_malloc((uint) (trees*sizeof(MI_DECODE_TREE)+
187
intervall_length*sizeof(uchar)),
190
intervall_buff=(uchar*) (share->decode_trees+trees);
195
- Quick decode tables
196
- Temporary decode table
197
- Compressed data file header cache
198
This segment will be reallocated after construction of the tables.
200
length=(uint) (elements*2+trees*(1 << myisam_quick_table_bits));
201
if (!(share->decode_tables=(uint16*)
202
my_malloc((length + OFFSET_TABLE_SIZE) * sizeof(uint16) +
203
(uint) (share->pack.header_length - sizeof(header)),
204
MYF(MY_WME | MY_ZEROFILL))))
206
tmp_buff=share->decode_tables+length;
207
disk_cache= (uchar*) (tmp_buff+OFFSET_TABLE_SIZE);
209
if (my_read(file,disk_cache,
210
(uint) (share->pack.header_length-sizeof(header)),
214
huff_tree_bits=max_bit(trees ? trees-1 : 0);
215
init_bit_buffer(&bit_buff, disk_cache,
216
(uint) (share->pack.header_length-sizeof(header)));
217
/* Read new info for each field */
218
for (i=0 ; i < share->base.fields ; i++)
220
share->rec[i].base_type=(enum en_fieldtype) get_bits(&bit_buff,5);
221
share->rec[i].pack_type=(uint) get_bits(&bit_buff,6);
222
share->rec[i].space_length_bits=get_bits(&bit_buff,5);
223
share->rec[i].huff_tree=share->decode_trees+(uint) get_bits(&bit_buff,
225
share->rec[i].unpack=get_unpack_function(share->rec+i);
227
skip_to_next_byte(&bit_buff);
229
Construct the decoding tables from the file header. Keep track of
232
decode_table=share->decode_tables;
233
for (i=0 ; i < trees ; i++)
234
if (read_huff_table(&bit_buff,share->decode_trees+i,&decode_table,
235
&intervall_buff,tmp_buff))
237
/* Reallocate the decoding tables to the used size. */
238
decode_table=(uint16*)
239
my_realloc((uchar*) share->decode_tables,
240
(uint) ((uchar*) decode_table - (uchar*) share->decode_tables),
241
MYF(MY_HOLD_ON_ERROR));
242
/* Fix the table addresses in the tree heads. */
244
long diff=PTR_BYTE_DIFF(decode_table,share->decode_tables);
245
share->decode_tables=decode_table;
246
for (i=0 ; i < trees ; i++)
247
share->decode_trees[i].table=ADD_TO_PTR(share->decode_trees[i].table,
251
/* Fix record-ref-length for keys */
254
for (i=0 ; i < share->base.keys ; i++)
256
MI_KEYDEF *keyinfo= &share->keyinfo[i];
257
keyinfo->keylength+= (uint16) diff_length;
258
keyinfo->minlength+= (uint16) diff_length;
259
keyinfo->maxlength+= (uint16) diff_length;
260
keyinfo->seg[keyinfo->keysegs].length= (uint16) rec_reflength;
262
if (share->ft2_keyinfo.seg)
264
MI_KEYDEF *ft2_keyinfo= &share->ft2_keyinfo;
265
ft2_keyinfo->keylength+= (uint16) diff_length;
266
ft2_keyinfo->minlength+= (uint16) diff_length;
267
ft2_keyinfo->maxlength+= (uint16) diff_length;
271
if (bit_buff.error || bit_buff.pos < bit_buff.end)
277
my_errno=HA_ERR_WRONG_IN_RECORD;
279
my_free((uchar*) share->decode_tables,MYF(0));
281
my_free((uchar*) share->decode_trees,MYF(0));
288
Read a huff-code-table from datafile.
292
bit_buff Bit buffer pointing at start of the
293
decoding table in the file header cache.
294
decode_tree Pointer to the decode tree head.
295
decode_table IN/OUT Address of a pointer to the next free space.
296
intervall_buff IN/OUT Address of a pointer to the next unused values.
297
tmp_buff Buffer for temporary extraction of a full
298
decoding table as read from bit_buff.
305
static uint read_huff_table(MI_BIT_BUFF *bit_buff, MI_DECODE_TREE *decode_tree,
306
uint16 **decode_table, uchar **intervall_buff,
309
uint min_chr,elements,char_bits,offset_bits,size,intervall_length,table_bits,
313
if (!get_bits(bit_buff,1))
315
/* Byte value compression. */
316
min_chr=get_bits(bit_buff,8);
317
elements=get_bits(bit_buff,9);
318
char_bits=get_bits(bit_buff,5);
319
offset_bits=get_bits(bit_buff,5);
329
/* Distinct column value compression. */
331
elements=get_bits(bit_buff,15);
332
intervall_length=get_bits(bit_buff,16);
333
char_bits=get_bits(bit_buff,5);
334
offset_bits=get_bits(bit_buff,5);
335
decode_tree->quick_table_bits=0;
340
for (end=ptr+size ; ptr < end ; ptr++)
342
if (get_bit(bit_buff))
344
*ptr= (uint16) get_bits(bit_buff,offset_bits);
345
if ((ptr + *ptr >= end) || !*ptr)
351
*ptr= (uint16) (IS_CHAR + (get_bits(bit_buff,char_bits) + min_chr));
353
skip_to_next_byte(bit_buff);
355
decode_tree->table= *decode_table;
356
decode_tree->intervalls= *intervall_buff;
357
if (! intervall_length)
359
/* Byte value compression. ptr started from tmp_buff. */
360
/* Find longest Huffman code from begin to end of tree in bits. */
361
table_bits= find_longest_bitstream(tmp_buff, ptr);
362
if (table_bits >= OFFSET_TABLE_SIZE)
364
if (table_bits > myisam_quick_table_bits)
365
table_bits=myisam_quick_table_bits;
367
next_free_offset= (1 << table_bits);
368
make_quick_table(*decode_table,tmp_buff,&next_free_offset,0,table_bits,
370
(*decode_table)+= next_free_offset;
371
decode_tree->quick_table_bits=table_bits;
375
/* Distinct column value compression. ptr started from *decode_table */
378
get_bits() moves some bytes to a cache buffer in advance. May need
381
bit_buff->pos-= bit_buff->bits/8;
382
/* Copy the distinct column values from the buffer. */
383
memcpy(*intervall_buff,bit_buff->pos,(size_t) intervall_length);
384
(*intervall_buff)+=intervall_length;
385
bit_buff->pos+=intervall_length;
393
Make a quick_table for faster decoding.
397
to_table Target quick_table and remaining decode table.
398
decode_table Source Huffman (sub-)tree within tmp_buff.
399
next_free_offset IN/OUT Next free offset from to_table.
400
Starts behind quick_table on the top-level.
401
value Huffman bits found so far.
402
bits Remaining bits to be collected.
403
max_bits Total number of bits to collect (table_bits).
407
The quick table is an array of 16-bit values. There exists one value
408
for each possible code representable by max_bits (table_bits) bits.
409
In most cases table_bits is 9. So there are 512 16-bit values.
411
If the high-order bit (16) is set (IS_CHAR) then the array slot for
412
this value is a valid Huffman code for a resulting byte value.
414
The low-order 8 bits (1..8) are the resulting byte value.
416
Bits 9..14 are the length of the Huffman code for this byte value.
417
This means so many bits from the input stream were needed to
418
represent this byte value. The remaining bits belong to later
419
Huffman codes. This also means that for every Huffman code shorter
420
than table_bits there are multiple entires in the array, which
421
differ just in the unused bits.
423
If the high-order bit (16) is clear (0) then the remaining bits are
424
the position of the remaining Huffman decode tree segment behind the
431
static void make_quick_table(uint16 *to_table, uint16 *decode_table,
432
uint *next_free_offset, uint value, uint bits,
436
When down the table to the requested maximum, copy the rest of the
442
Remaining left Huffman tree segment starts behind quick table.
443
Remaining right Huffman tree segment starts behind left segment.
445
to_table[value]= (uint16) *next_free_offset;
447
Re-construct the remaining Huffman tree segment at
448
next_free_offset in to_table.
450
*next_free_offset= copy_decode_table(to_table, *next_free_offset,
455
/* Descent on the left side. Left side bits are clear (0). */
456
if (!(*decode_table & IS_CHAR))
458
/* Not a leaf. Follow the pointer. */
459
make_quick_table(to_table, decode_table + *decode_table,
460
next_free_offset, value, bits, max_bits);
465
A leaf. A Huffman code is complete. Fill the quick_table
466
array for all possible bit strings starting with this Huffman
469
fill_quick_table(to_table + value, bits, max_bits, (uint) *decode_table);
472
/* Descent on the right side. Right side bits are set (1). */
475
if (!(*decode_table & IS_CHAR))
477
/* Not a leaf. Follow the pointer. */
478
make_quick_table(to_table, decode_table + *decode_table,
479
next_free_offset, value, bits, max_bits);
484
A leaf. A Huffman code is complete. Fill the quick_table
485
array for all possible bit strings starting with this Huffman
488
fill_quick_table(to_table + value, bits, max_bits, (uint) *decode_table);
496
Fill quick_table for all possible values starting with this Huffman code.
500
table Target quick_table position.
501
bits Unused bits from max_bits.
502
max_bits Total number of bits to collect (table_bits).
503
value The byte encoded by the found Huffman code.
507
Fill the segment (all slots) of the quick_table array with the
508
resulting value for the found Huffman code. There are as many slots
509
as there are combinations representable by the unused bits.
511
In most cases we use 9 table bits. Assume a 3-bit Huffman code. Then
512
there are 6 unused bits. Hence we fill 2**6 = 64 slots with the
519
static void fill_quick_table(uint16 *table, uint bits, uint max_bits,
525
Bits 1..8 of value represent the decoded byte value.
526
Bits 9..14 become the length of the Huffman code for this byte value.
527
Bit 16 flags a valid code (IS_CHAR).
529
value|= (max_bits - bits) << 8 | IS_CHAR;
531
for (end= table + ((my_ptrdiff_t) 1 << bits); table < end; table++)
533
*table= (uint16) value;
540
Reconstruct a decode subtree at the target position.
544
to_pos Target quick_table and remaining decode table.
545
offset Next free offset from to_pos.
546
decode_table Source Huffman subtree within tmp_buff.
549
Pointers in the decode tree are relative to the pointers position.
552
next free offset from to_pos.
555
static uint copy_decode_table(uint16 *to_pos, uint offset,
556
uint16 *decode_table)
558
uint prev_offset= offset;
560
/* Descent on the left side. */
561
if (!(*decode_table & IS_CHAR))
563
/* Set a pointer to the next target node. */
565
/* Copy the left hand subtree there. */
566
offset=copy_decode_table(to_pos,offset+2,decode_table+ *decode_table);
570
/* Copy the byte value. */
571
to_pos[offset]= *decode_table;
572
/* Step behind this node. */
576
/* Descent on the right side. */
578
if (!(*decode_table & IS_CHAR))
580
/* Set a pointer to the next free target node. */
581
to_pos[prev_offset+1]=(uint16) (offset-prev_offset-1);
582
/* Copy the right hand subtree to the entry of that node. */
583
offset=copy_decode_table(to_pos,offset,decode_table+ *decode_table);
587
/* Copy the byte value. */
588
to_pos[prev_offset+1]= *decode_table;
595
Find the length of the longest Huffman code in this table in bits.
598
find_longest_bitstream()
599
table Code (sub-)table start.
600
end End of code table.
604
Recursively follow the branch(es) of the code pair on every level of
605
the tree until two byte values (and no branch) are found. Add one to
606
each level when returning back from each recursion stage.
608
'end' is used for error checking only. A clean tree terminates
609
before reaching 'end'. Hence the exact value of 'end' is not too
610
important. However having it higher than necessary could lead to
611
misbehaviour should 'next' jump into the dirty area.
614
length Length of longest Huffman code in bits.
615
>= OFFSET_TABLE_SIZE Error, broken tree. It does not end before 'end'.
618
static uint find_longest_bitstream(uint16 *table, uint16 *end)
623
if (!(*table & IS_CHAR))
625
uint16 *next= table + *table;
626
if (next > end || next == table)
628
return OFFSET_TABLE_SIZE;
630
length= find_longest_bitstream(next, end) + 1;
633
if (!(*table & IS_CHAR))
635
uint16 *next= table + *table;
636
if (next > end || next == table)
638
return OFFSET_TABLE_SIZE;
640
length2= find_longest_bitstream(next, end) + 1;
641
length=max(length,length2);
648
Read record from datafile.
651
_mi_read_pack_record()
652
info A pointer to MI_INFO.
653
filepos File offset of the record.
654
buf RETURN The buffer to receive the record.
658
HA_ERR_WRONG_IN_RECORD or -1 on error
661
int _mi_read_pack_record(MI_INFO *info, my_off_t filepos, uchar *buf)
663
MI_BLOCK_INFO block_info;
666
if (filepos == HA_OFFSET_ERROR)
667
return(-1); /* _search() didn't find record */
670
if (_mi_pack_get_block_info(info, &info->bit_buff, &block_info,
671
&info->rec_buff, file, filepos))
673
if (my_read(file,(uchar*) info->rec_buff + block_info.offset ,
674
block_info.rec_len - block_info.offset, MYF(MY_NABP)))
676
info->update|= HA_STATE_AKTIV;
677
return(_mi_pack_rec_unpack(info, &info->bit_buff, buf,
678
info->rec_buff, block_info.rec_len));
680
my_errno=HA_ERR_WRONG_IN_RECORD;
687
int _mi_pack_rec_unpack(register MI_INFO *info, MI_BIT_BUFF *bit_buff,
688
register uchar *to, uchar *from, ulong reclength)
691
register MI_COLUMNDEF *end;
692
MI_COLUMNDEF *current_field;
693
MYISAM_SHARE *share=info->s;
695
init_bit_buffer(bit_buff, (uchar*) from, reclength);
697
for (current_field=share->rec, end=current_field+share->base.fields ;
698
current_field < end ;
699
current_field++,to=end_field)
701
end_field=to+current_field->length;
702
(*current_field->unpack)(current_field, bit_buff, (uchar*) to,
705
if (!bit_buff->error &&
706
bit_buff->pos - bit_buff->bits / 8 == bit_buff->end)
708
info->update&= ~HA_STATE_AKTIV;
709
return(my_errno=HA_ERR_WRONG_IN_RECORD);
710
} /* _mi_pack_rec_unpack */
713
/* Return function to unpack field */
715
static void (*get_unpack_function(MI_COLUMNDEF *rec))
716
(MI_COLUMNDEF *, MI_BIT_BUFF *, uchar *, uchar *)
718
switch (rec->base_type) {
719
case FIELD_SKIP_ZERO:
720
if (rec->pack_type & PACK_TYPE_ZERO_FILL)
721
return &uf_zerofill_skip_zero;
722
return &uf_skip_zero;
724
if (rec->pack_type & PACK_TYPE_SPACE_FIELDS)
725
return &uf_space_normal;
726
if (rec->pack_type & PACK_TYPE_ZERO_FILL)
727
return &uf_zerofill_normal;
728
return &decode_bytes;
729
case FIELD_SKIP_ENDSPACE:
730
if (rec->pack_type & PACK_TYPE_SPACE_FIELDS)
732
if (rec->pack_type & PACK_TYPE_SELECTED)
733
return &uf_space_endspace_selected;
734
return &uf_space_endspace;
736
if (rec->pack_type & PACK_TYPE_SELECTED)
737
return &uf_endspace_selected;
739
case FIELD_SKIP_PRESPACE:
740
if (rec->pack_type & PACK_TYPE_SPACE_FIELDS)
742
if (rec->pack_type & PACK_TYPE_SELECTED)
743
return &uf_space_prespace_selected;
744
return &uf_space_prespace;
746
if (rec->pack_type & PACK_TYPE_SELECTED)
747
return &uf_prespace_selected;
751
case FIELD_INTERVALL:
752
return &uf_intervall;
759
if (rec->length <= 256) /* 255 + 1 byte length */
764
return 0; /* This should never happend */
768
/* The different functions to unpack a field */
770
static void uf_zerofill_skip_zero(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
771
uchar *to, uchar *end)
773
if (get_bit(bit_buff))
774
bzero((char*) to,(uint) (end-to));
777
end-=rec->space_length_bits;
778
decode_bytes(rec,bit_buff,to,end);
779
bzero((char*) end,rec->space_length_bits);
783
static void uf_skip_zero(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
786
if (get_bit(bit_buff))
787
bzero((char*) to,(uint) (end-to));
789
decode_bytes(rec,bit_buff,to,end);
792
static void uf_space_normal(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
795
if (get_bit(bit_buff))
796
bfill((uchar*) to,(end-to),' ');
798
decode_bytes(rec,bit_buff,to,end);
801
static void uf_space_endspace_selected(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
802
uchar *to, uchar *end)
805
if (get_bit(bit_buff))
806
bfill((uchar*) to,(end-to),' ');
809
if (get_bit(bit_buff))
811
if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
816
if (to+spaces != end)
817
decode_bytes(rec,bit_buff,to,end-spaces);
818
bfill((uchar*) end-spaces,spaces,' ');
821
decode_bytes(rec,bit_buff,to,end);
825
static void uf_endspace_selected(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
826
uchar *to, uchar *end)
829
if (get_bit(bit_buff))
831
if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
836
if (to+spaces != end)
837
decode_bytes(rec,bit_buff,to,end-spaces);
838
bfill((uchar*) end-spaces,spaces,' ');
841
decode_bytes(rec,bit_buff,to,end);
844
static void uf_space_endspace(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
848
if (get_bit(bit_buff))
849
bfill((uchar*) to,(end-to),' ');
852
if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
857
if (to+spaces != end)
858
decode_bytes(rec,bit_buff,to,end-spaces);
859
bfill((uchar*) end-spaces,spaces,' ');
863
static void uf_endspace(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
867
if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
872
if (to+spaces != end)
873
decode_bytes(rec,bit_buff,to,end-spaces);
874
bfill((uchar*) end-spaces,spaces,' ');
877
static void uf_space_prespace_selected(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
878
uchar *to, uchar *end)
881
if (get_bit(bit_buff))
882
bfill((uchar*) to,(end-to),' ');
885
if (get_bit(bit_buff))
887
if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
892
bfill((uchar*) to,spaces,' ');
893
if (to+spaces != end)
894
decode_bytes(rec,bit_buff,to+spaces,end);
897
decode_bytes(rec,bit_buff,to,end);
902
static void uf_prespace_selected(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
903
uchar *to, uchar *end)
906
if (get_bit(bit_buff))
908
if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
913
bfill((uchar*) to,spaces,' ');
914
if (to+spaces != end)
915
decode_bytes(rec,bit_buff,to+spaces,end);
918
decode_bytes(rec,bit_buff,to,end);
922
static void uf_space_prespace(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
926
if (get_bit(bit_buff))
927
bfill((uchar*) to,(end-to),' ');
930
if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
935
bfill((uchar*) to,spaces,' ');
936
if (to+spaces != end)
937
decode_bytes(rec,bit_buff,to+spaces,end);
941
static void uf_prespace(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
945
if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
950
bfill((uchar*) to,spaces,' ');
951
if (to+spaces != end)
952
decode_bytes(rec,bit_buff,to+spaces,end);
955
static void uf_zerofill_normal(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
958
end-=rec->space_length_bits;
959
decode_bytes(rec,bit_buff,(uchar*) to,end);
960
bzero((char*) end,rec->space_length_bits);
963
static void uf_constant(MI_COLUMNDEF *rec,
964
MI_BIT_BUFF *bit_buff __attribute__((unused)),
968
memcpy(to,rec->huff_tree->intervalls,(size_t) (end-to));
971
static void uf_intervall(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
974
register uint field_length=(uint) (end-to);
975
memcpy(to,rec->huff_tree->intervalls+field_length*decode_pos(bit_buff,
977
(size_t) field_length);
982
static void uf_zero(MI_COLUMNDEF *rec __attribute__((unused)),
983
MI_BIT_BUFF *bit_buff __attribute__((unused)),
984
uchar *to, uchar *end)
986
bzero((char*) to,(uint) (end-to));
989
static void uf_blob(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
990
uchar *to, uchar *end)
992
if (get_bit(bit_buff))
993
bzero((uchar*) to,(end-to));
996
ulong length=get_bits(bit_buff,rec->space_length_bits);
997
uint pack_length=(uint) (end-to)-portable_sizeof_char_ptr;
998
if (bit_buff->blob_pos+length > bit_buff->blob_end)
1001
bzero((uchar*) to,(end-to));
1004
decode_bytes(rec,bit_buff,bit_buff->blob_pos,bit_buff->blob_pos+length);
1005
_my_store_blob_length((uchar*) to,pack_length,length);
1006
memcpy_fixed((char*) to+pack_length,(char*) &bit_buff->blob_pos,
1008
bit_buff->blob_pos+=length;
1013
static void uf_varchar1(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
1014
uchar *to, uchar *end __attribute__((unused)))
1016
if (get_bit(bit_buff))
1017
to[0]= 0; /* Zero lengths */
1020
ulong length=get_bits(bit_buff,rec->space_length_bits);
1021
*to= (uchar) length;
1022
decode_bytes(rec,bit_buff,to+1,to+1+length);
1027
static void uf_varchar2(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
1028
uchar *to, uchar *end __attribute__((unused)))
1030
if (get_bit(bit_buff))
1031
to[0]=to[1]=0; /* Zero lengths */
1034
ulong length=get_bits(bit_buff,rec->space_length_bits);
1035
int2store(to,length);
1036
decode_bytes(rec,bit_buff,to+2,to+2+length);
1040
/* Functions to decode of buffer of bits */
1042
#if BITS_SAVED == 64
1044
static void decode_bytes(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,uchar *to,
1047
register uint bits,low_byte;
1048
register uint16 *pos;
1049
register uint table_bits,table_and;
1050
MI_DECODE_TREE *decode_tree;
1052
decode_tree=rec->decode_tree;
1053
bits=bit_buff->bits; /* Save in reg for quicker access */
1054
table_bits=decode_tree->quick_table_bits;
1055
table_and= (1 << table_bits)-1;
1061
if (bit_buff->pos > bit_buff->end+4)
1064
return; /* Can't be right */
1066
bit_buff->current_byte= (bit_buff->current_byte << 32) +
1067
((((uint) bit_buff->pos[3])) +
1068
(((uint) bit_buff->pos[2]) << 8) +
1069
(((uint) bit_buff->pos[1]) << 16) +
1070
(((uint) bit_buff->pos[0]) << 24));
1075
First use info in quick_table.
1077
The quick table is an array of 16-bit values. There exists one
1078
value for each possible code representable by table_bits bits.
1079
In most cases table_bits is 9. So there are 512 16-bit values.
1081
If the high-order bit (16) is set (IS_CHAR) then the array slot
1082
for this value is a valid Huffman code for a resulting byte value.
1084
The low-order 8 bits (1..8) are the resulting byte value.
1086
Bits 9..14 are the length of the Huffman code for this byte value.
1087
This means so many bits from the input stream were needed to
1088
represent this byte value. The remaining bits belong to later
1089
Huffman codes. This also means that for every Huffman code shorter
1090
than table_bits there are multiple entires in the array, which
1091
differ just in the unused bits.
1093
If the high-order bit (16) is clear (0) then the remaining bits are
1094
the position of the remaining Huffman decode tree segment behind the
1097
low_byte=(uint) (bit_buff->current_byte >> (bits - table_bits)) & table_and;
1098
low_byte=decode_tree->table[low_byte];
1099
if (low_byte & IS_CHAR)
1102
All Huffman codes of less or equal table_bits length are in the
1103
quick table. This is one of them.
1105
*to++ = (low_byte & 255); /* Found char in quick table */
1106
bits-= ((low_byte >> 8) & 31); /* Remove bits used */
1109
{ /* Map through rest of decode-table */
1110
/* This means that the Huffman code must be longer than table_bits. */
1111
pos=decode_tree->table+low_byte;
1113
/* NOTE: decode_bytes_test_bit() is a macro wich contains a break !!! */
1116
low_byte=(uint) (bit_buff->current_byte >> (bits-8));
1117
decode_bytes_test_bit(0);
1118
decode_bytes_test_bit(1);
1119
decode_bytes_test_bit(2);
1120
decode_bytes_test_bit(3);
1121
decode_bytes_test_bit(4);
1122
decode_bytes_test_bit(5);
1123
decode_bytes_test_bit(6);
1124
decode_bytes_test_bit(7);
1129
} while (to != end);
1131
bit_buff->bits=bits;
1137
static void decode_bytes(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
1140
register uint bits,low_byte;
1141
register uint16 *pos;
1142
register uint table_bits,table_and;
1143
MI_DECODE_TREE *decode_tree;
1145
decode_tree=rec->huff_tree;
1146
bits=bit_buff->bits; /* Save in reg for quicker access */
1147
table_bits=decode_tree->quick_table_bits;
1148
table_and= (1 << table_bits)-1;
1152
if (bits < table_bits)
1154
if (bit_buff->pos > bit_buff->end+1)
1157
return; /* Can't be right */
1159
#if BITS_SAVED == 32
1160
bit_buff->current_byte= (bit_buff->current_byte << 24) +
1161
(((uint) ((uchar) bit_buff->pos[2]))) +
1162
(((uint) ((uchar) bit_buff->pos[1])) << 8) +
1163
(((uint) ((uchar) bit_buff->pos[0])) << 16);
1167
if (bits) /* We must have at leasts 9 bits */
1169
bit_buff->current_byte= (bit_buff->current_byte << 8) +
1170
(uint) ((uchar) bit_buff->pos[0]);
1176
bit_buff->current_byte= ((uint) ((uchar) bit_buff->pos[0]) << 8) +
1177
((uint) ((uchar) bit_buff->pos[1]));
1183
/* First use info in quick_table */
1184
low_byte=(bit_buff->current_byte >> (bits - table_bits)) & table_and;
1185
low_byte=decode_tree->table[low_byte];
1186
if (low_byte & IS_CHAR)
1188
*to++ = (low_byte & 255); /* Found char in quick table */
1189
bits-= ((low_byte >> 8) & 31); /* Remove bits used */
1192
{ /* Map through rest of decode-table */
1193
pos=decode_tree->table+low_byte;
1198
{ /* We don't need to check end */
1199
#if BITS_SAVED == 32
1200
bit_buff->current_byte= (bit_buff->current_byte << 24) +
1201
(((uint) ((uchar) bit_buff->pos[2]))) +
1202
(((uint) ((uchar) bit_buff->pos[1])) << 8) +
1203
(((uint) ((uchar) bit_buff->pos[0])) << 16);
1207
bit_buff->current_byte= (bit_buff->current_byte << 8) +
1208
(uint) ((uchar) bit_buff->pos[0]);
1213
low_byte=(uint) (bit_buff->current_byte >> (bits-8));
1214
decode_bytes_test_bit(0);
1215
decode_bytes_test_bit(1);
1216
decode_bytes_test_bit(2);
1217
decode_bytes_test_bit(3);
1218
decode_bytes_test_bit(4);
1219
decode_bytes_test_bit(5);
1220
decode_bytes_test_bit(6);
1221
decode_bytes_test_bit(7);
1224
*to++ = (uchar) *pos;
1226
} while (to != end);
1228
bit_buff->bits=bits;
1231
#endif /* BIT_SAVED == 64 */
1234
static uint decode_pos(MI_BIT_BUFF *bit_buff, MI_DECODE_TREE *decode_tree)
1236
uint16 *pos=decode_tree->table;
1239
if (get_bit(bit_buff))
1242
return (uint) (*pos & ~IS_CHAR);
1248
int _mi_read_rnd_pack_record(MI_INFO *info, uchar *buf,
1249
register my_off_t filepos,
1250
my_bool skip_deleted_blocks)
1253
MI_BLOCK_INFO block_info;
1254
MYISAM_SHARE *share=info->s;
1256
if (filepos >= info->state->data_file_length)
1258
my_errno= HA_ERR_END_OF_FILE;
1262
if (info->opt_flag & READ_CACHE_USED)
1264
if (_mi_read_cache(&info->rec_cache, (uchar*) block_info.header,
1265
filepos, share->pack.ref_length,
1266
skip_deleted_blocks ? READING_NEXT : 0))
1268
b_type=_mi_pack_get_block_info(info, &info->bit_buff, &block_info,
1269
&info->rec_buff, -1, filepos);
1272
b_type=_mi_pack_get_block_info(info, &info->bit_buff, &block_info,
1273
&info->rec_buff, info->dfile, filepos);
1275
goto err; /* Error code is already set */
1277
if (info->opt_flag & READ_CACHE_USED)
1279
if (_mi_read_cache(&info->rec_cache, (uchar*) info->rec_buff,
1280
block_info.filepos, block_info.rec_len,
1281
skip_deleted_blocks ? READING_NEXT : 0))
1286
if (my_read(info->dfile,(uchar*) info->rec_buff + block_info.offset,
1287
block_info.rec_len-block_info.offset,
1291
info->packed_length=block_info.rec_len;
1292
info->lastpos=filepos;
1293
info->nextpos=block_info.filepos+block_info.rec_len;
1294
info->update|= HA_STATE_AKTIV | HA_STATE_KEY_CHANGED;
1296
return (_mi_pack_rec_unpack(info, &info->bit_buff, buf,
1297
info->rec_buff, block_info.rec_len));
1303
/* Read and process header from a huff-record-file */
1305
uint _mi_pack_get_block_info(MI_INFO *myisam, MI_BIT_BUFF *bit_buff,
1306
MI_BLOCK_INFO *info, uchar **rec_buff_p,
1307
File file, my_off_t filepos)
1309
uchar *header=info->header;
1310
uint head_length, ref_length= 0;
1314
ref_length=myisam->s->pack.ref_length;
1316
We can't use my_pread() here because mi_read_rnd_pack_record assumes
1319
VOID(my_seek(file,filepos,MY_SEEK_SET,MYF(0)));
1320
if (my_read(file, header,ref_length,MYF(MY_NABP)))
1321
return BLOCK_FATAL_ERROR;
1323
head_length= read_pack_length((uint) myisam->s->pack.version, header,
1325
if (myisam->s->base.blobs)
1327
head_length+= read_pack_length((uint) myisam->s->pack.version,
1328
header + head_length, &info->blob_len);
1330
Ensure that the record buffer is big enough for the compressed
1331
record plus all expanded blobs. [We do not have an extra buffer
1332
for the resulting blobs. Sigh.]
1334
if (!(mi_alloc_rec_buff(myisam,info->rec_len + info->blob_len,
1336
return BLOCK_FATAL_ERROR; /* not enough memory */
1337
bit_buff->blob_pos= (uchar*) *rec_buff_p + info->rec_len;
1338
bit_buff->blob_end= bit_buff->blob_pos + info->blob_len;
1339
myisam->blob_length=info->blob_len;
1341
info->filepos=filepos+head_length;
1344
info->offset=min(info->rec_len, ref_length - head_length);
1345
memcpy(*rec_buff_p, header + head_length, info->offset);
1351
/* rutines for bit buffer */
1352
/* Note buffer must be 6 byte bigger than longest row */
1354
static void init_bit_buffer(MI_BIT_BUFF *bit_buff, uchar *buffer, uint length)
1356
bit_buff->pos=buffer;
1357
bit_buff->end=buffer+length;
1358
bit_buff->bits=bit_buff->error=0;
1359
bit_buff->current_byte=0; /* Avoid purify errors */
1362
static uint fill_and_get_bits(MI_BIT_BUFF *bit_buff, uint count)
1365
count-=bit_buff->bits;
1366
tmp=(bit_buff->current_byte & mask[bit_buff->bits]) << count;
1367
fill_buffer(bit_buff);
1368
bit_buff->bits=BITS_SAVED - count;
1369
return tmp+(bit_buff->current_byte >> (BITS_SAVED - count));
1372
/* Fill in empty bit_buff->current_byte from buffer */
1373
/* Sets bit_buff->error if buffer is exhausted */
1375
static void fill_buffer(MI_BIT_BUFF *bit_buff)
1377
if (bit_buff->pos >= bit_buff->end)
1380
bit_buff->current_byte=0;
1383
#if BITS_SAVED == 64
1384
bit_buff->current_byte= ((((uint) ((uchar) bit_buff->pos[7]))) +
1385
(((uint) ((uchar) bit_buff->pos[6])) << 8) +
1386
(((uint) ((uchar) bit_buff->pos[5])) << 16) +
1387
(((uint) ((uchar) bit_buff->pos[4])) << 24) +
1389
((((uint) ((uchar) bit_buff->pos[3]))) +
1390
(((uint) ((uchar) bit_buff->pos[2])) << 8) +
1391
(((uint) ((uchar) bit_buff->pos[1])) << 16) +
1392
(((uint) ((uchar) bit_buff->pos[0])) << 24)) << 32));
1395
#if BITS_SAVED == 32
1396
bit_buff->current_byte= (((uint) ((uchar) bit_buff->pos[3])) +
1397
(((uint) ((uchar) bit_buff->pos[2])) << 8) +
1398
(((uint) ((uchar) bit_buff->pos[1])) << 16) +
1399
(((uint) ((uchar) bit_buff->pos[0])) << 24));
1402
bit_buff->current_byte= (uint) (((uint) ((uchar) bit_buff->pos[1]))+
1403
(((uint) ((uchar) bit_buff->pos[0])) << 8));
1409
/* Get number of bits neaded to represent value */
1411
static uint max_bit(register uint value)
1413
register uint power=1;
1421
/*****************************************************************************
1422
Some redefined functions to handle files when we are using memmap
1423
*****************************************************************************/
1424
#ifdef HAVE_SYS_MMAN_H
1425
#include <sys/mman.h>
1430
static int _mi_read_mempack_record(MI_INFO *info,my_off_t filepos,uchar *buf);
1431
static int _mi_read_rnd_mempack_record(MI_INFO*, uchar *,my_off_t, my_bool);
1433
my_bool _mi_memmap_file(MI_INFO *info)
1435
MYISAM_SHARE *share=info->s;
1437
if (!info->s->file_map)
1439
if (my_seek(info->dfile,0L,MY_SEEK_END,MYF(0)) <
1440
share->state.state.data_file_length+MEMMAP_EXTRA_MARGIN)
1444
if (mi_dynmap_file(info, share->state.state.data_file_length))
1447
info->opt_flag|= MEMMAP_USED;
1448
info->read_record= share->read_record= _mi_read_mempack_record;
1449
share->read_rnd= _mi_read_rnd_mempack_record;
1454
void _mi_unmap_file(MI_INFO *info)
1456
VOID(my_munmap((char*) info->s->file_map,
1457
(size_t) info->s->mmaped_length + MEMMAP_EXTRA_MARGIN));
1461
static uchar *_mi_mempack_get_block_info(MI_INFO *myisam, MI_BIT_BUFF *bit_buff,
1462
MI_BLOCK_INFO *info, uchar **rec_buff_p,
1465
header+= read_pack_length((uint) myisam->s->pack.version, header,
1467
if (myisam->s->base.blobs)
1469
header+= read_pack_length((uint) myisam->s->pack.version, header,
1471
/* mi_alloc_rec_buff sets my_errno on error */
1472
if (!(mi_alloc_rec_buff(myisam, info->blob_len,
1474
return 0; /* not enough memory */
1475
bit_buff->blob_pos= (uchar*) *rec_buff_p;
1476
bit_buff->blob_end= (uchar*) *rec_buff_p + info->blob_len;
1482
static int _mi_read_mempack_record(MI_INFO *info, my_off_t filepos, uchar *buf)
1484
MI_BLOCK_INFO block_info;
1485
MYISAM_SHARE *share=info->s;
1488
if (filepos == HA_OFFSET_ERROR)
1489
return(-1); /* _search() didn't find record */
1491
if (!(pos= (uchar*) _mi_mempack_get_block_info(info, &info->bit_buff,
1492
&block_info, &info->rec_buff,
1493
(uchar*) share->file_map+
1496
return(_mi_pack_rec_unpack(info, &info->bit_buff, buf,
1497
pos, block_info.rec_len));
1502
static int _mi_read_rnd_mempack_record(MI_INFO *info, uchar *buf,
1503
register my_off_t filepos,
1504
my_bool skip_deleted_blocks
1505
__attribute__((unused)))
1507
MI_BLOCK_INFO block_info;
1508
MYISAM_SHARE *share=info->s;
1511
if (filepos >= share->state.state.data_file_length)
1513
my_errno=HA_ERR_END_OF_FILE;
1516
if (!(pos= (uchar*) _mi_mempack_get_block_info(info, &info->bit_buff,
1517
&block_info, &info->rec_buff,
1519
(start=share->file_map+
1522
info->packed_length=block_info.rec_len;
1523
info->lastpos=filepos;
1524
info->nextpos=filepos+(uint) (pos-start)+block_info.rec_len;
1525
info->update|= HA_STATE_AKTIV | HA_STATE_KEY_CHANGED;
1527
return (_mi_pack_rec_unpack(info, &info->bit_buff, buf,
1528
pos, block_info.rec_len));
1533
#endif /* HAVE_MMAP */
1535
/* Save length of row */
1537
uint save_pack_length(uint version, uchar *block_buff, ulong length)
1541
*(uchar*) block_buff= (uchar) length;
1544
if (length <= 65535)
1546
*(uchar*) block_buff=254;
1547
int2store(block_buff+1,(uint) length);
1550
*(uchar*) block_buff=255;
1551
if (version == 1) /* old format */
1553
assert(length <= 0xFFFFFF);
1554
int3store(block_buff + 1, (ulong) length);
1559
int4store(block_buff + 1, (ulong) length);
1565
uint read_pack_length(uint version, const uchar *buf, ulong *length)
1572
else if (buf[0] == 254)
1574
*length= uint2korr(buf + 1);
1577
if (version == 1) /* old format */
1579
*length= uint3korr(buf + 1);
1584
*length= uint4korr(buf + 1);
1590
uint calc_pack_length(uint version, ulong length)
1592
return (length < 254) ? 1 : (length < 65536) ? 3 : (version == 1) ? 4 : 5;
added
removed
storage/myisam/mi_packrec.c
