← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/myisam/mi_packrec.c

  • Committer: Monty Taylor
  • Date: 2008-08-04 19:37:18 UTC
  • mto: (261.2.2 codestyle)
  • mto: This revision was merged to the branch mainline in revision 262.
  • Revision ID: monty@inaugust.com-20080804193718-f0rz13uli4429ozb
Changed gettext_noop() to N_()

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/myisam/mi_packrec.c
 
1
/* Copyright (C) 2000-2006 MySQL 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 "myisamdef.h"
 
19
 
 
20
#define IS_CHAR ((uint) 32768)          /* Bit if char (not offset) in tree */
 
21
 
 
22
/* Some definitions to keep in sync with myisampack.c */
 
23
#define HEAD_LENGTH     32              /* Length of fixed header */
 
24
 
 
25
#if INT_MAX > 32767
 
26
#define BITS_SAVED 32
 
27
#define MAX_QUICK_TABLE_BITS 9          /* Because we may shift in 24 bits */
 
28
#else
 
29
#define BITS_SAVED 16
 
30
#define MAX_QUICK_TABLE_BITS 6
 
31
#endif
 
32
 
 
33
#define get_bit(BU) ((BU)->bits ? \
 
34
                     (BU)->current_byte & ((mi_bit_type) 1 << --(BU)->bits) :\
 
35
                     (fill_buffer(BU), (BU)->bits= BITS_SAVED-1,\
 
36
                      (BU)->current_byte & ((mi_bit_type) 1 << (BITS_SAVED-1))))
 
37
#define skip_to_next_byte(BU) ((BU)->bits&=~7)
 
38
#define get_bits(BU,count) (((BU)->bits >= count) ? (((BU)->current_byte >> ((BU)->bits-=count)) & mask[count]) : fill_and_get_bits(BU,count))
 
39
 
 
40
#define decode_bytes_test_bit(bit) \
 
41
  if (low_byte & (1 << (7-bit))) \
 
42
    pos++; \
 
43
  if (*pos & IS_CHAR) \
 
44
  { bits-=(bit+1); break; } \
 
45
  pos+= *pos
 
46
 
 
47
/* Size in uint16_t of a Huffman tree for byte compression of 256 byte values. */
 
48
#define OFFSET_TABLE_SIZE 512
 
49
 
 
50
static uint read_huff_table(MI_BIT_BUFF *bit_buff,MI_DECODE_TREE *decode_tree,
 
51
                            uint16_t **decode_table,uchar **intervall_buff,
 
52
                            uint16_t *tmp_buff);
 
53
static void make_quick_table(uint16_t *to_table,uint16_t *decode_table,
 
54
                             uint *next_free,uint value,uint bits,
 
55
                             uint max_bits);
 
56
static void fill_quick_table(uint16_t *table,uint bits, uint max_bits,
 
57
                             uint value);
 
58
static uint copy_decode_table(uint16_t *to_pos,uint offset,
 
59
                              uint16_t *decode_table);
 
60
static uint find_longest_bitstream(uint16_t *table, uint16_t *end);
 
61
static void (*get_unpack_function(MI_COLUMNDEF *rec))(MI_COLUMNDEF *field,
 
62
                                                    MI_BIT_BUFF *buff,
 
63
                                                    uchar *to,
 
64
                                                    uchar *end);
 
65
static void uf_zerofill_skip_zero(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
66
                                   uchar *to,uchar *end);
 
67
static void uf_skip_zero(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
68
                          uchar *to,uchar *end);
 
69
static void uf_space_normal(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
70
                            uchar *to,uchar *end);
 
71
static void uf_space_endspace_selected(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
72
                                       uchar *to, uchar *end);
 
73
static void uf_endspace_selected(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
74
                                 uchar *to,uchar *end);
 
75
static void uf_space_endspace(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
76
                              uchar *to,uchar *end);
 
77
static void uf_endspace(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
78
                        uchar *to,uchar *end);
 
79
static void uf_space_prespace_selected(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
80
                                       uchar *to, uchar *end);
 
81
static void uf_prespace_selected(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
82
                                 uchar *to,uchar *end);
 
83
static void uf_space_prespace(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
84
                              uchar *to,uchar *end);
 
85
static void uf_prespace(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
86
                        uchar *to,uchar *end);
 
87
static void uf_zerofill_normal(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
88
                               uchar *to,uchar *end);
 
89
static void uf_constant(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
90
                        uchar *to,uchar *end);
 
91
static void uf_intervall(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
92
                         uchar *to,uchar *end);
 
93
static void uf_zero(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
94
                    uchar *to,uchar *end);
 
95
static void uf_blob(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
 
96
                    uchar *to, uchar *end);
 
97
static void uf_varchar1(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
 
98
                        uchar *to, uchar *end);
 
99
static void uf_varchar2(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
 
100
                        uchar *to, uchar *end);
 
101
static void decode_bytes(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,
 
102
                         uchar *to,uchar *end);
 
103
static uint decode_pos(MI_BIT_BUFF *bit_buff,MI_DECODE_TREE *decode_tree);
 
104
static void init_bit_buffer(MI_BIT_BUFF *bit_buff,uchar *buffer,uint length);
 
105
static uint fill_and_get_bits(MI_BIT_BUFF *bit_buff,uint count);
 
106
static void fill_buffer(MI_BIT_BUFF *bit_buff);
 
107
static uint max_bit(uint value);
 
108
#ifdef HAVE_MMAP
 
109
static uchar *_mi_mempack_get_block_info(MI_INFO *myisam, MI_BIT_BUFF *bit_buff,
 
110
                                         MI_BLOCK_INFO *info, uchar **rec_buff_p,
 
111
                                         uchar *header);
 
112
#endif
 
113
 
 
114
static mi_bit_type mask[]=
 
115
{
 
116
   0x00000000,
 
117
   0x00000001, 0x00000003, 0x00000007, 0x0000000f,
 
118
   0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff,
 
119
   0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff,
 
120
   0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff,
 
121
#if BITS_SAVED > 16
 
122
   0x0001ffff, 0x0003ffff, 0x0007ffff, 0x000fffff,
 
123
   0x001fffff, 0x003fffff, 0x007fffff, 0x00ffffff,
 
124
   0x01ffffff, 0x03ffffff, 0x07ffffff, 0x0fffffff,
 
125
   0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff,
 
126
#endif
 
127
 };
 
128
 
 
129
 
 
130
        /* Read all packed info, allocate memory and fix field structs */
 
131
 
 
132
my_bool _mi_read_pack_info(MI_INFO *info, bool fix_keys)
 
133
{
 
134
  File file;
 
135
  int diff_length;
 
136
  uint i,trees,huff_tree_bits,rec_reflength,length;
 
137
  uint16_t *decode_table,*tmp_buff;
 
138
  ulong elements,intervall_length;
 
139
  uchar *disk_cache;
 
140
  uchar *intervall_buff;
 
141
  uchar header[HEAD_LENGTH];
 
142
  MYISAM_SHARE *share=info->s;
 
143
  MI_BIT_BUFF bit_buff;
 
144
 
 
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;
 
149
 
 
150
  file=info->dfile;
 
151
  my_errno=0;
 
152
  if (my_read(file,(uchar*) header,sizeof(header),MYF(MY_NABP)))
 
153
  {
 
154
    if (!my_errno)
 
155
      my_errno=HA_ERR_END_OF_FILE;
 
156
    goto err0;
 
157
  }
 
158
  /* Only the first three bytes of magic number are independent of version. */
 
159
  if (memcmp((uchar*) header, (uchar*) myisam_pack_file_magic, 3))
 
160
  {
 
161
    my_errno=HA_ERR_WRONG_IN_RECORD;
 
162
    goto err0;
 
163
  }
 
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;
 
174
  if (fix_keys)
 
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;
 
179
 
 
180
  /*
 
181
    Memory segment #1:
 
182
    - Decode tree heads
 
183
    - Distinct column values
 
184
  */
 
185
  if (!(share->decode_trees=(MI_DECODE_TREE*)
 
186
        my_malloc((uint) (trees*sizeof(MI_DECODE_TREE)+
 
187
                          intervall_length*sizeof(uchar)),
 
188
                  MYF(MY_WME))))
 
189
    goto err0;
 
190
  intervall_buff=(uchar*) (share->decode_trees+trees);
 
191
 
 
192
  /*
 
193
    Memory segment #2:
 
194
    - Decode tables
 
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.
 
199
  */
 
200
  length=(uint) (elements*2+trees*(1 << myisam_quick_table_bits));
 
201
  if (!(share->decode_tables=(uint16_t*)
 
202
        my_malloc((length + OFFSET_TABLE_SIZE) * sizeof(uint16_t) +
 
203
                  (uint) (share->pack.header_length - sizeof(header)),
 
204
                  MYF(MY_WME | MY_ZEROFILL))))
 
205
    goto err1;
 
206
  tmp_buff=share->decode_tables+length;
 
207
  disk_cache= (uchar*) (tmp_buff+OFFSET_TABLE_SIZE);
 
208
 
 
209
  if (my_read(file,disk_cache,
 
210
              (uint) (share->pack.header_length-sizeof(header)),
 
211
              MYF(MY_NABP)))
 
212
    goto err2;
 
213
 
 
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++)
 
219
  {
 
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,
 
224
                                                                huff_tree_bits);
 
225
    share->rec[i].unpack=get_unpack_function(share->rec+i);
 
226
  }
 
227
  skip_to_next_byte(&bit_buff);
 
228
  /*
 
229
    Construct the decoding tables from the file header. Keep track of
 
230
    the used memory.
 
231
  */
 
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))
 
236
      goto err3;
 
237
  /* Reallocate the decoding tables to the used size. */
 
238
  decode_table=(uint16_t*)
 
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. */
 
243
  {
 
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,
 
248
                                              diff, uint16_t*);
 
249
  }
 
250
 
 
251
  /* Fix record-ref-length for keys */
 
252
  if (fix_keys)
 
253
  {
 
254
    for (i=0 ; i < share->base.keys ; i++)
 
255
    {
 
256
      MI_KEYDEF *keyinfo= &share->keyinfo[i];
 
257
      keyinfo->keylength+= (uint16_t) diff_length;
 
258
      keyinfo->minlength+= (uint16_t) diff_length;
 
259
      keyinfo->maxlength+= (uint16_t) diff_length;
 
260
      keyinfo->seg[keyinfo->keysegs].length= (uint16_t) rec_reflength;
 
261
    }
 
262
    if (share->ft2_keyinfo.seg)
 
263
    {
 
264
      MI_KEYDEF *ft2_keyinfo= &share->ft2_keyinfo;
 
265
      ft2_keyinfo->keylength+= (uint16_t) diff_length;
 
266
      ft2_keyinfo->minlength+= (uint16_t) diff_length;
 
267
      ft2_keyinfo->maxlength+= (uint16_t) diff_length;
 
268
    }
 
269
  }
 
270
 
 
271
  if (bit_buff.error || bit_buff.pos < bit_buff.end)
 
272
    goto err3;
 
273
 
 
274
  return(0);
 
275
 
 
276
err3:
 
277
  my_errno=HA_ERR_WRONG_IN_RECORD;
 
278
err2:
 
279
  my_free((uchar*) share->decode_tables,MYF(0));
 
280
err1:
 
281
  my_free((uchar*) share->decode_trees,MYF(0));
 
282
err0:
 
283
  return(1);
 
284
}
 
285
 
 
286
 
 
287
/*
 
288
  Read a huff-code-table from datafile.
 
289
 
 
290
  SYNOPSIS
 
291
    read_huff_table()
 
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.
 
299
 
 
300
  RETURN
 
301
    0           OK.
 
302
    1           Error.
 
303
*/
 
304
 
 
305
static uint read_huff_table(MI_BIT_BUFF *bit_buff, MI_DECODE_TREE *decode_tree,
 
306
                            uint16_t **decode_table, uchar **intervall_buff,
 
307
                            uint16_t *tmp_buff)
 
308
{
 
309
  uint min_chr,elements,char_bits,offset_bits,size,intervall_length,table_bits,
 
310
  next_free_offset;
 
311
  uint16_t *ptr,*end;
 
312
 
 
313
  if (!get_bits(bit_buff,1))
 
314
  {
 
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);
 
320
    intervall_length=0;
 
321
    ptr=tmp_buff;
 
322
    if (elements > 256)
 
323
    {
 
324
      return(1);
 
325
    }
 
326
  }
 
327
  else
 
328
  {
 
329
    /* Distinct column value compression. */
 
330
    min_chr=0;
 
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;
 
336
    ptr= *decode_table;
 
337
  }
 
338
  size=elements*2-2;
 
339
 
 
340
  for (end=ptr+size ; ptr < end ; ptr++)
 
341
  {
 
342
    if (get_bit(bit_buff))
 
343
    {
 
344
      *ptr= (uint16_t) get_bits(bit_buff,offset_bits);
 
345
      if ((ptr + *ptr >= end) || !*ptr)
 
346
      {
 
347
        return(1);
 
348
      }
 
349
    }
 
350
    else
 
351
      *ptr= (uint16_t) (IS_CHAR + (get_bits(bit_buff,char_bits) + min_chr));
 
352
  }
 
353
  skip_to_next_byte(bit_buff);
 
354
 
 
355
  decode_tree->table= *decode_table;
 
356
  decode_tree->intervalls= *intervall_buff;
 
357
  if (! intervall_length)
 
358
  {
 
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)
 
363
      return(1);
 
364
    if (table_bits > myisam_quick_table_bits)
 
365
      table_bits=myisam_quick_table_bits;
 
366
 
 
367
    next_free_offset= (1 << table_bits);
 
368
    make_quick_table(*decode_table,tmp_buff,&next_free_offset,0,table_bits,
 
369
                     table_bits);
 
370
    (*decode_table)+= next_free_offset;
 
371
    decode_tree->quick_table_bits=table_bits;
 
372
  }
 
373
  else
 
374
  {
 
375
    /* Distinct column value compression. ptr started from *decode_table */
 
376
    (*decode_table)=end;
 
377
    /*
 
378
      get_bits() moves some bytes to a cache buffer in advance. May need
 
379
      to step back.
 
380
    */
 
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;
 
386
    bit_buff->bits=0;
 
387
  }
 
388
  return(0);
 
389
}
 
390
 
 
391
 
 
392
/*
 
393
  Make a quick_table for faster decoding.
 
394
 
 
395
  SYNOPSIS
 
396
    make_quick_table()
 
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).
 
404
 
 
405
  DESCRIPTION
 
406
 
 
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.
 
410
 
 
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.
 
413
 
 
414
    The low-order 8 bits (1..8) are the resulting byte value.
 
415
 
 
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.
 
422
 
 
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
 
425
    quick table.
 
426
 
 
427
  RETURN
 
428
    void
 
429
*/
 
430
 
 
431
static void make_quick_table(uint16_t *to_table, uint16_t *decode_table,
 
432
                             uint *next_free_offset, uint value, uint bits,
 
433
                             uint max_bits)
 
434
{
 
435
  /*
 
436
    When down the table to the requested maximum, copy the rest of the
 
437
    Huffman table.
 
438
  */
 
439
  if (!bits--)
 
440
  {
 
441
    /*
 
442
      Remaining left  Huffman tree segment starts behind quick table.
 
443
      Remaining right Huffman tree segment starts behind left segment.
 
444
    */
 
445
    to_table[value]= (uint16_t) *next_free_offset;
 
446
    /*
 
447
      Re-construct the remaining Huffman tree segment at
 
448
      next_free_offset in to_table.
 
449
    */
 
450
    *next_free_offset= copy_decode_table(to_table, *next_free_offset,
 
451
                                         decode_table);
 
452
    return;
 
453
  }
 
454
 
 
455
  /* Descent on the left side. Left side bits are clear (0). */
 
456
  if (!(*decode_table & IS_CHAR))
 
457
  {
 
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);
 
461
  }
 
462
  else
 
463
  {
 
464
    /*
 
465
      A leaf. A Huffman code is complete. Fill the quick_table
 
466
      array for all possible bit strings starting with this Huffman
 
467
      code.
 
468
    */
 
469
    fill_quick_table(to_table + value, bits, max_bits, (uint) *decode_table);
 
470
  }
 
471
 
 
472
  /* Descent on the right side. Right side bits are set (1). */
 
473
  decode_table++;
 
474
  value|= (1 << bits);
 
475
  if (!(*decode_table & IS_CHAR))
 
476
  {
 
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);
 
480
  }
 
481
  else
 
482
  {
 
483
    /*
 
484
      A leaf. A Huffman code is complete. Fill the quick_table
 
485
      array for all possible bit strings starting with this Huffman
 
486
      code.
 
487
    */
 
488
    fill_quick_table(to_table + value, bits, max_bits, (uint) *decode_table);
 
489
  }
 
490
 
 
491
  return;
 
492
}
 
493
 
 
494
 
 
495
/*
 
496
  Fill quick_table for all possible values starting with this Huffman code.
 
497
 
 
498
  SYNOPSIS
 
499
    fill_quick_table()
 
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.
 
504
 
 
505
  DESCRIPTION
 
506
 
 
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.
 
510
 
 
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
 
513
    value.
 
514
 
 
515
  RETURN
 
516
    void
 
517
*/
 
518
 
 
519
static void fill_quick_table(uint16_t *table, uint bits, uint max_bits,
 
520
                             uint value)
 
521
{
 
522
  uint16_t *end;
 
523
 
 
524
  /*
 
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).
 
528
  */
 
529
  value|= (max_bits - bits) << 8 | IS_CHAR;
 
530
 
 
531
  for (end= table + ((my_ptrdiff_t) 1 << bits); table < end; table++)
 
532
  {
 
533
    *table= (uint16_t) value;
 
534
  }
 
535
  return;
 
536
}
 
537
 
 
538
 
 
539
/*
 
540
  Reconstruct a decode subtree at the target position.
 
541
 
 
542
  SYNOPSIS
 
543
    copy_decode_table()
 
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.
 
547
 
 
548
  NOTE
 
549
    Pointers in the decode tree are relative to the pointers position.
 
550
 
 
551
  RETURN
 
552
    next free offset from to_pos.
 
553
*/
 
554
 
 
555
static uint copy_decode_table(uint16_t *to_pos, uint offset,
 
556
                              uint16_t *decode_table)
 
557
{
 
558
  uint prev_offset= offset;
 
559
 
 
560
  /* Descent on the left side. */
 
561
  if (!(*decode_table & IS_CHAR))
 
562
  {
 
563
    /* Set a pointer to the next target node. */
 
564
    to_pos[offset]=2;
 
565
    /* Copy the left hand subtree there. */
 
566
    offset=copy_decode_table(to_pos,offset+2,decode_table+ *decode_table);
 
567
  }
 
568
  else
 
569
  {
 
570
    /* Copy the byte value. */
 
571
    to_pos[offset]= *decode_table;
 
572
    /* Step behind this node. */
 
573
    offset+=2;
 
574
  }
 
575
 
 
576
  /* Descent on the right side. */
 
577
  decode_table++;
 
578
  if (!(*decode_table & IS_CHAR))
 
579
  {
 
580
    /* Set a pointer to the next free target node. */
 
581
    to_pos[prev_offset+1]=(uint16_t) (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);
 
584
  }
 
585
  else
 
586
  {
 
587
    /* Copy the byte value. */
 
588
    to_pos[prev_offset+1]= *decode_table;
 
589
  }
 
590
  return(offset);
 
591
}
 
592
 
 
593
 
 
594
/*
 
595
  Find the length of the longest Huffman code in this table in bits.
 
596
 
 
597
  SYNOPSIS
 
598
    find_longest_bitstream()
 
599
      table                     Code (sub-)table start.
 
600
      end                       End of code table.
 
601
 
 
602
  IMPLEMENTATION
 
603
 
 
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.
 
607
 
 
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.
 
612
 
 
613
  RETURN
 
614
    length                  Length of longest Huffman code in bits.
 
615
    >= OFFSET_TABLE_SIZE    Error, broken tree. It does not end before 'end'.
 
616
*/
 
617
 
 
618
static uint find_longest_bitstream(uint16_t *table, uint16_t *end)
 
619
{
 
620
  uint length= 1;
 
621
  uint length2;
 
622
 
 
623
  if (!(*table & IS_CHAR))
 
624
  {
 
625
    uint16_t *next= table + *table;
 
626
    if (next > end || next == table)
 
627
    {
 
628
      return OFFSET_TABLE_SIZE;
 
629
    }
 
630
    length= find_longest_bitstream(next, end) + 1;
 
631
  }
 
632
  table++;
 
633
  if (!(*table & IS_CHAR))
 
634
  {
 
635
    uint16_t *next= table + *table;
 
636
    if (next > end || next == table)
 
637
    {
 
638
      return OFFSET_TABLE_SIZE;
 
639
    }
 
640
    length2= find_longest_bitstream(next, end) + 1;
 
641
    length=max(length,length2);
 
642
  }
 
643
  return length;
 
644
}
 
645
 
 
646
 
 
647
/*
 
648
  Read record from datafile.
 
649
 
 
650
  SYNOPSIS
 
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.
 
655
 
 
656
  RETURN
 
657
    0                                   on success
 
658
    HA_ERR_WRONG_IN_RECORD or -1        on error
 
659
*/
 
660
 
 
661
int _mi_read_pack_record(MI_INFO *info, my_off_t filepos, uchar *buf)
 
662
{
 
663
  MI_BLOCK_INFO block_info;
 
664
  File file;
 
665
 
 
666
  if (filepos == HA_OFFSET_ERROR)
 
667
    return(-1);                 /* _search() didn't find record */
 
668
 
 
669
  file=info->dfile;
 
670
  if (_mi_pack_get_block_info(info, &info->bit_buff, &block_info,
 
671
                              &info->rec_buff, file, filepos))
 
672
    goto err;
 
673
  if (my_read(file,(uchar*) info->rec_buff + block_info.offset ,
 
674
              block_info.rec_len - block_info.offset, MYF(MY_NABP)))
 
675
    goto panic;
 
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));
 
679
panic:
 
680
  my_errno=HA_ERR_WRONG_IN_RECORD;
 
681
err:
 
682
  return(-1);
 
683
}
 
684
 
 
685
 
 
686
 
 
687
int _mi_pack_rec_unpack(register MI_INFO *info, MI_BIT_BUFF *bit_buff,
 
688
                        register uchar *to, uchar *from, ulong reclength)
 
689
{
 
690
  uchar *end_field;
 
691
  register MI_COLUMNDEF *end;
 
692
  MI_COLUMNDEF *current_field;
 
693
  MYISAM_SHARE *share=info->s;
 
694
 
 
695
  init_bit_buffer(bit_buff, (uchar*) from, reclength);
 
696
 
 
697
  for (current_field=share->rec, end=current_field+share->base.fields ;
 
698
       current_field < end ;
 
699
       current_field++,to=end_field)
 
700
  {
 
701
    end_field=to+current_field->length;
 
702
    (*current_field->unpack)(current_field, bit_buff, (uchar*) to,
 
703
                             (uchar*) end_field);
 
704
  }
 
705
  if (!bit_buff->error &&
 
706
      bit_buff->pos - bit_buff->bits / 8 == bit_buff->end)
 
707
    return(0);
 
708
  info->update&= ~HA_STATE_AKTIV;
 
709
  return(my_errno=HA_ERR_WRONG_IN_RECORD);
 
710
} /* _mi_pack_rec_unpack */
 
711
 
 
712
 
 
713
        /* Return function to unpack field */
 
714
 
 
715
static void (*get_unpack_function(MI_COLUMNDEF *rec))
 
716
(MI_COLUMNDEF *, MI_BIT_BUFF *, uchar *, uchar *)
 
717
{
 
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;
 
723
  case FIELD_NORMAL:
 
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)
 
731
    {
 
732
      if (rec->pack_type & PACK_TYPE_SELECTED)
 
733
        return &uf_space_endspace_selected;
 
734
      return &uf_space_endspace;
 
735
    }
 
736
    if (rec->pack_type & PACK_TYPE_SELECTED)
 
737
      return &uf_endspace_selected;
 
738
    return &uf_endspace;
 
739
  case FIELD_SKIP_PRESPACE:
 
740
    if (rec->pack_type & PACK_TYPE_SPACE_FIELDS)
 
741
    {
 
742
      if (rec->pack_type & PACK_TYPE_SELECTED)
 
743
        return &uf_space_prespace_selected;
 
744
      return &uf_space_prespace;
 
745
    }
 
746
    if (rec->pack_type & PACK_TYPE_SELECTED)
 
747
      return &uf_prespace_selected;
 
748
    return &uf_prespace;
 
749
  case FIELD_CONSTANT:
 
750
    return &uf_constant;
 
751
  case FIELD_INTERVALL:
 
752
    return &uf_intervall;
 
753
  case FIELD_ZERO:
 
754
  case FIELD_CHECK:
 
755
    return &uf_zero;
 
756
  case FIELD_BLOB:
 
757
    return &uf_blob;
 
758
  case FIELD_VARCHAR:
 
759
    if (rec->length <= 256)                      /* 255 + 1 byte length */
 
760
      return &uf_varchar1;
 
761
    return &uf_varchar2;
 
762
  case FIELD_LAST:
 
763
  default:
 
764
    return 0;                   /* This should never happend */
 
765
  }
 
766
}
 
767
 
 
768
        /* The different functions to unpack a field */
 
769
 
 
770
static void uf_zerofill_skip_zero(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
 
771
                                   uchar *to, uchar *end)
 
772
{
 
773
  if (get_bit(bit_buff))
 
774
    memset((char*) to, 0, (uint) (end-to));
 
775
  else
 
776
  {
 
777
    end-=rec->space_length_bits;
 
778
    decode_bytes(rec,bit_buff,to,end);
 
779
    memset((char*) end, 0, rec->space_length_bits);
 
780
  }
 
781
}
 
782
 
 
783
static void uf_skip_zero(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
 
784
                          uchar *end)
 
785
{
 
786
  if (get_bit(bit_buff))
 
787
    memset((char*) to, 0, (uint) (end-to));
 
788
  else
 
789
    decode_bytes(rec,bit_buff,to,end);
 
790
}
 
791
 
 
792
static void uf_space_normal(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
 
793
                            uchar *end)
 
794
{
 
795
  if (get_bit(bit_buff))
 
796
    memset((uchar*) to, ' ', (end-to));
 
797
  else
 
798
    decode_bytes(rec,bit_buff,to,end);
 
799
}
 
800
 
 
801
static void uf_space_endspace_selected(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
 
802
                                       uchar *to, uchar *end)
 
803
{
 
804
  uint spaces;
 
805
  if (get_bit(bit_buff))
 
806
    memset((uchar*) to, ' ', (end-to));
 
807
  else
 
808
  {
 
809
    if (get_bit(bit_buff))
 
810
    {
 
811
      if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
 
812
      {
 
813
        bit_buff->error=1;
 
814
        return;
 
815
      }
 
816
      if (to+spaces != end)
 
817
        decode_bytes(rec,bit_buff,to,end-spaces);
 
818
      memset((uchar*) end-spaces, ' ', spaces);
 
819
    }
 
820
    else
 
821
      decode_bytes(rec,bit_buff,to,end);
 
822
  }
 
823
}
 
824
 
 
825
static void uf_endspace_selected(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
 
826
                                 uchar *to, uchar *end)
 
827
{
 
828
  uint spaces;
 
829
  if (get_bit(bit_buff))
 
830
  {
 
831
    if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
 
832
    {
 
833
      bit_buff->error=1;
 
834
      return;
 
835
    }
 
836
    if (to+spaces != end)
 
837
      decode_bytes(rec,bit_buff,to,end-spaces);
 
838
    memset((uchar*) end-spaces, ' ', spaces);
 
839
  }
 
840
  else
 
841
    decode_bytes(rec,bit_buff,to,end);
 
842
}
 
843
 
 
844
static void uf_space_endspace(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
 
845
                              uchar *end)
 
846
{
 
847
  uint spaces;
 
848
  if (get_bit(bit_buff))
 
849
    memset((uchar*) to, ' ', (end-to));
 
850
  else
 
851
  {
 
852
    if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
 
853
    {
 
854
      bit_buff->error=1;
 
855
      return;
 
856
    }
 
857
    if (to+spaces != end)
 
858
      decode_bytes(rec,bit_buff,to,end-spaces);
 
859
    memset((uchar*) end-spaces, ' ', spaces);
 
860
  }
 
861
}
 
862
 
 
863
static void uf_endspace(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
 
864
                        uchar *end)
 
865
{
 
866
  uint spaces;
 
867
  if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
 
868
  {
 
869
    bit_buff->error=1;
 
870
    return;
 
871
  }
 
872
  if (to+spaces != end)
 
873
    decode_bytes(rec,bit_buff,to,end-spaces);
 
874
  memset((uchar*) end-spaces, ' ', spaces);
 
875
}
 
876
 
 
877
static void uf_space_prespace_selected(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
 
878
                                       uchar *to, uchar *end)
 
879
{
 
880
  uint spaces;
 
881
  if (get_bit(bit_buff))
 
882
    memset((uchar*) to, ' ', (end-to));
 
883
  else
 
884
  {
 
885
    if (get_bit(bit_buff))
 
886
    {
 
887
      if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
 
888
      {
 
889
        bit_buff->error=1;
 
890
        return;
 
891
      }
 
892
      memset((uchar*) to, ' ', spaces);
 
893
      if (to+spaces != end)
 
894
        decode_bytes(rec,bit_buff,to+spaces,end);
 
895
    }
 
896
    else
 
897
      decode_bytes(rec,bit_buff,to,end);
 
898
  }
 
899
}
 
900
 
 
901
 
 
902
static void uf_prespace_selected(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
 
903
                                 uchar *to, uchar *end)
 
904
{
 
905
  uint spaces;
 
906
  if (get_bit(bit_buff))
 
907
  {
 
908
    if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
 
909
    {
 
910
      bit_buff->error=1;
 
911
      return;
 
912
    }
 
913
    memset((uchar*) to, ' ', spaces);
 
914
    if (to+spaces != end)
 
915
      decode_bytes(rec,bit_buff,to+spaces,end);
 
916
  }
 
917
  else
 
918
    decode_bytes(rec,bit_buff,to,end);
 
919
}
 
920
 
 
921
 
 
922
static void uf_space_prespace(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
 
923
                              uchar *end)
 
924
{
 
925
  uint spaces;
 
926
  if (get_bit(bit_buff))
 
927
    memset((uchar*) to, ' ', (end-to));
 
928
  else
 
929
  {
 
930
    if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
 
931
    {
 
932
      bit_buff->error=1;
 
933
      return;
 
934
    }
 
935
    memset((uchar*) to, ' ', spaces);
 
936
    if (to+spaces != end)
 
937
      decode_bytes(rec,bit_buff,to+spaces,end);
 
938
  }
 
939
}
 
940
 
 
941
static void uf_prespace(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
 
942
                        uchar *end)
 
943
{
 
944
  uint spaces;
 
945
  if ((spaces=get_bits(bit_buff,rec->space_length_bits))+to > end)
 
946
  {
 
947
    bit_buff->error=1;
 
948
    return;
 
949
  }
 
950
  memset((uchar*) to, ' ', spaces);
 
951
  if (to+spaces != end)
 
952
    decode_bytes(rec,bit_buff,to+spaces,end);
 
953
}
 
954
 
 
955
static void uf_zerofill_normal(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
 
956
                               uchar *end)
 
957
{
 
958
  end-=rec->space_length_bits;
 
959
  decode_bytes(rec,bit_buff,(uchar*) to,end);
 
960
  memset((char*) end, 0, rec->space_length_bits);
 
961
}
 
962
 
 
963
static void uf_constant(MI_COLUMNDEF *rec,
 
964
                        MI_BIT_BUFF *bit_buff __attribute__((unused)),
 
965
                        uchar *to,
 
966
                        uchar *end)
 
967
{
 
968
  memcpy(to,rec->huff_tree->intervalls,(size_t) (end-to));
 
969
}
 
970
 
 
971
static void uf_intervall(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
 
972
                         uchar *end)
 
973
{
 
974
  register uint field_length=(uint) (end-to);
 
975
  memcpy(to,rec->huff_tree->intervalls+field_length*decode_pos(bit_buff,
 
976
                                                               rec->huff_tree),
 
977
         (size_t) field_length);
 
978
}
 
979
 
 
980
 
 
981
/*ARGSUSED*/
 
982
static void uf_zero(MI_COLUMNDEF *rec __attribute__((unused)),
 
983
                    MI_BIT_BUFF *bit_buff __attribute__((unused)),
 
984
                    uchar *to, uchar *end)
 
985
{
 
986
  memset((char*) to, 0, (uint) (end-to));
 
987
}
 
988
 
 
989
static void uf_blob(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
 
990
                    uchar *to, uchar *end)
 
991
{
 
992
  if (get_bit(bit_buff))
 
993
    memset((uchar*) to, 0, (end-to));
 
994
  else
 
995
  {
 
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)
 
999
    {
 
1000
      bit_buff->error=1;
 
1001
      memset((uchar*) to, 0, (end-to));
 
1002
      return;
 
1003
    }
 
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((char*) to+pack_length,(char*) &bit_buff->blob_pos,
 
1007
           sizeof(char*));
 
1008
    bit_buff->blob_pos+=length;
 
1009
  }
 
1010
}
 
1011
 
 
1012
 
 
1013
static void uf_varchar1(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
 
1014
                       uchar *to, uchar *end __attribute__((unused)))
 
1015
{
 
1016
  if (get_bit(bit_buff))
 
1017
    to[0]= 0;                           /* Zero lengths */
 
1018
  else
 
1019
  {
 
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);
 
1023
  }
 
1024
}
 
1025
 
 
1026
 
 
1027
static void uf_varchar2(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff,
 
1028
                       uchar *to, uchar *end __attribute__((unused)))
 
1029
{
 
1030
  if (get_bit(bit_buff))
 
1031
    to[0]=to[1]=0;                              /* Zero lengths */
 
1032
  else
 
1033
  {
 
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);
 
1037
  }
 
1038
}
 
1039
 
 
1040
        /* Functions to decode of buffer of bits */
 
1041
 
 
1042
#if BITS_SAVED == 64
 
1043
 
 
1044
static void decode_bytes(MI_COLUMNDEF *rec,MI_BIT_BUFF *bit_buff,uchar *to,
 
1045
                         uchar *end)
 
1046
{
 
1047
  register uint bits,low_byte;
 
1048
  register uint16_t *pos;
 
1049
  register uint table_bits,table_and;
 
1050
  MI_DECODE_TREE *decode_tree;
 
1051
 
 
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;
 
1056
 
 
1057
  do
 
1058
  {
 
1059
    if (bits <= 32)
 
1060
    {
 
1061
      if (bit_buff->pos > bit_buff->end+4)
 
1062
      {
 
1063
        bit_buff->error=1;
 
1064
        return;                         /* Can't be right */
 
1065
      }
 
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));
 
1071
      bit_buff->pos+=4;
 
1072
      bits+=32;
 
1073
    }
 
1074
    /*
 
1075
      First use info in quick_table.
 
1076
 
 
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.
 
1080
 
 
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.
 
1083
 
 
1084
      The low-order 8 bits (1..8) are the resulting byte value.
 
1085
 
 
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.
 
1092
 
 
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
 
1095
      quick table.
 
1096
    */
 
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)
 
1100
    {
 
1101
      /*
 
1102
        All Huffman codes of less or equal table_bits length are in the
 
1103
        quick table. This is one of them.
 
1104
      */
 
1105
      *to++ = (low_byte & 255);         /* Found char in quick table */
 
1106
      bits-=  ((low_byte >> 8) & 31);   /* Remove bits used */
 
1107
    }
 
1108
    else
 
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;
 
1112
      bits-=table_bits;
 
1113
      /* NOTE: decode_bytes_test_bit() is a macro wich contains a break !!! */
 
1114
      for (;;)
 
1115
      {
 
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);
 
1125
        bits-=8;
 
1126
      }
 
1127
      *to++ = *pos;
 
1128
    }
 
1129
  } while (to != end);
 
1130
 
 
1131
  bit_buff->bits=bits;
 
1132
  return;
 
1133
}
 
1134
 
 
1135
#else
 
1136
 
 
1137
static void decode_bytes(MI_COLUMNDEF *rec, MI_BIT_BUFF *bit_buff, uchar *to,
 
1138
                         uchar *end)
 
1139
{
 
1140
  register uint bits,low_byte;
 
1141
  register uint16_t *pos;
 
1142
  register uint table_bits,table_and;
 
1143
  MI_DECODE_TREE *decode_tree;
 
1144
 
 
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;
 
1149
 
 
1150
  do
 
1151
  {
 
1152
    if (bits < table_bits)
 
1153
    {
 
1154
      if (bit_buff->pos > bit_buff->end+1)
 
1155
      {
 
1156
        bit_buff->error=1;
 
1157
        return;                         /* Can't be right */
 
1158
      }
 
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);
 
1164
      bit_buff->pos+=3;
 
1165
      bits+=24;
 
1166
#else
 
1167
      if (bits)                         /* We must have at leasts 9 bits */
 
1168
      {
 
1169
        bit_buff->current_byte=  (bit_buff->current_byte << 8) +
 
1170
          (uint) ((uchar) bit_buff->pos[0]);
 
1171
        bit_buff->pos++;
 
1172
        bits+=8;
 
1173
      }
 
1174
      else
 
1175
      {
 
1176
        bit_buff->current_byte= ((uint) ((uchar) bit_buff->pos[0]) << 8) +
 
1177
          ((uint) ((uchar) bit_buff->pos[1]));
 
1178
        bit_buff->pos+=2;
 
1179
        bits+=16;
 
1180
      }
 
1181
#endif
 
1182
    }
 
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)
 
1187
    {
 
1188
      *to++ = (low_byte & 255);         /* Found char in quick table */
 
1189
      bits-=  ((low_byte >> 8) & 31);   /* Remove bits used */
 
1190
    }
 
1191
    else
 
1192
    {                                   /* Map through rest of decode-table */
 
1193
      pos=decode_tree->table+low_byte;
 
1194
      bits-=table_bits;
 
1195
      for (;;)
 
1196
      {
 
1197
        if (bits < 8)
 
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);
 
1204
          bit_buff->pos+=3;
 
1205
          bits+=24;
 
1206
#else
 
1207
          bit_buff->current_byte=  (bit_buff->current_byte << 8) +
 
1208
            (uint) ((uchar) bit_buff->pos[0]);
 
1209
          bit_buff->pos+=1;
 
1210
          bits+=8;
 
1211
#endif
 
1212
        }
 
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);
 
1222
        bits-=8;
 
1223
      }
 
1224
      *to++ = (uchar) *pos;
 
1225
    }
 
1226
  } while (to != end);
 
1227
 
 
1228
  bit_buff->bits=bits;
 
1229
  return;
 
1230
}
 
1231
#endif /* BIT_SAVED == 64 */
 
1232
 
 
1233
 
 
1234
static uint decode_pos(MI_BIT_BUFF *bit_buff, MI_DECODE_TREE *decode_tree)
 
1235
{
 
1236
  uint16_t *pos=decode_tree->table;
 
1237
  for (;;)
 
1238
  {
 
1239
    if (get_bit(bit_buff))
 
1240
      pos++;
 
1241
    if (*pos & IS_CHAR)
 
1242
      return (uint) (*pos & ~IS_CHAR);
 
1243
    pos+= *pos;
 
1244
  }
 
1245
}
 
1246
 
 
1247
 
 
1248
int _mi_read_rnd_pack_record(MI_INFO *info, uchar *buf,
 
1249
                             register my_off_t filepos,
 
1250
                             my_bool skip_deleted_blocks)
 
1251
{
 
1252
  uint b_type;
 
1253
  MI_BLOCK_INFO block_info;
 
1254
  MYISAM_SHARE *share=info->s;
 
1255
 
 
1256
  if (filepos >= info->state->data_file_length)
 
1257
  {
 
1258
    my_errno= HA_ERR_END_OF_FILE;
 
1259
    goto err;
 
1260
  }
 
1261
 
 
1262
  if (info->opt_flag & READ_CACHE_USED)
 
1263
  {
 
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))
 
1267
      goto err;
 
1268
    b_type=_mi_pack_get_block_info(info, &info->bit_buff, &block_info,
 
1269
                                   &info->rec_buff, -1, filepos);
 
1270
  }
 
1271
  else
 
1272
    b_type=_mi_pack_get_block_info(info, &info->bit_buff, &block_info,
 
1273
                                   &info->rec_buff, info->dfile, filepos);
 
1274
  if (b_type)
 
1275
    goto err;                                   /* Error code is already set */
 
1276
 
 
1277
  if (info->opt_flag & READ_CACHE_USED)
 
1278
  {
 
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))
 
1282
      goto err;
 
1283
  }
 
1284
  else
 
1285
  {
 
1286
    if (my_read(info->dfile,(uchar*) info->rec_buff + block_info.offset,
 
1287
                block_info.rec_len-block_info.offset,
 
1288
                MYF(MY_NABP)))
 
1289
      goto err;
 
1290
  }
 
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;
 
1295
 
 
1296
  return (_mi_pack_rec_unpack(info, &info->bit_buff, buf,
 
1297
                                   info->rec_buff, block_info.rec_len));
 
1298
 err:
 
1299
  return(my_errno);
 
1300
}
 
1301
 
 
1302
 
 
1303
        /* Read and process header from a huff-record-file */
 
1304
 
 
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)
 
1308
{
 
1309
  uchar *header=info->header;
 
1310
  uint head_length, ref_length= 0;
 
1311
 
 
1312
  if (file >= 0)
 
1313
  {
 
1314
    ref_length=myisam->s->pack.ref_length;
 
1315
    /*
 
1316
      We can't use my_pread() here because mi_read_rnd_pack_record assumes
 
1317
      position is ok
 
1318
    */
 
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;
 
1322
  }
 
1323
  head_length= read_pack_length((uint) myisam->s->pack.version, header,
 
1324
                                &info->rec_len);
 
1325
  if (myisam->s->base.blobs)
 
1326
  {
 
1327
    head_length+= read_pack_length((uint) myisam->s->pack.version,
 
1328
                                   header + head_length, &info->blob_len);
 
1329
    /*
 
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.]
 
1333
    */
 
1334
    if (!(mi_alloc_rec_buff(myisam,info->rec_len + info->blob_len,
 
1335
                            rec_buff_p)))
 
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;
 
1340
  }
 
1341
  info->filepos=filepos+head_length;
 
1342
  if (file > 0)
 
1343
  {
 
1344
    info->offset=min(info->rec_len, ref_length - head_length);
 
1345
    memcpy(*rec_buff_p, header + head_length, info->offset);
 
1346
  }
 
1347
  return 0;
 
1348
}
 
1349
 
 
1350
 
 
1351
        /* rutines for bit buffer */
 
1352
        /* Note buffer must be 6 byte bigger than longest row */
 
1353
 
 
1354
static void init_bit_buffer(MI_BIT_BUFF *bit_buff, uchar *buffer, uint length)
 
1355
{
 
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 */
 
1360
}
 
1361
 
 
1362
static uint fill_and_get_bits(MI_BIT_BUFF *bit_buff, uint count)
 
1363
{
 
1364
  uint tmp;
 
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));
 
1370
}
 
1371
 
 
1372
        /* Fill in empty bit_buff->current_byte from buffer */
 
1373
        /* Sets bit_buff->error if buffer is exhausted */
 
1374
 
 
1375
static void fill_buffer(MI_BIT_BUFF *bit_buff)
 
1376
{
 
1377
  if (bit_buff->pos >= bit_buff->end)
 
1378
  {
 
1379
    bit_buff->error= 1;
 
1380
    bit_buff->current_byte=0;
 
1381
    return;
 
1382
  }
 
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) +
 
1388
                             ((uint64_t)
 
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));
 
1393
  bit_buff->pos+=8;
 
1394
#else
 
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));
 
1400
  bit_buff->pos+=4;
 
1401
#else
 
1402
  bit_buff->current_byte=  (uint) (((uint) ((uchar) bit_buff->pos[1]))+
 
1403
                                    (((uint) ((uchar) bit_buff->pos[0])) << 8));
 
1404
  bit_buff->pos+=2;
 
1405
#endif
 
1406
#endif
 
1407
}
 
1408
 
 
1409
        /* Get number of bits neaded to represent value */
 
1410
 
 
1411
static uint max_bit(register uint value)
 
1412
{
 
1413
  register uint power=1;
 
1414
 
 
1415
  while ((value>>=1))
 
1416
    power++;
 
1417
  return (power);
 
1418
}
 
1419
 
 
1420
 
 
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>
 
1426
#endif
 
1427
 
 
1428
#ifdef HAVE_MMAP
 
1429
 
 
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);
 
1432
 
 
1433
my_bool _mi_memmap_file(MI_INFO *info)
 
1434
{
 
1435
  MYISAM_SHARE *share=info->s;
 
1436
 
 
1437
  if (!info->s->file_map)
 
1438
  {
 
1439
    if (my_seek(info->dfile,0L,MY_SEEK_END,MYF(0)) <
 
1440
        share->state.state.data_file_length+MEMMAP_EXTRA_MARGIN)
 
1441
    {
 
1442
      return(0);
 
1443
    }
 
1444
    if (mi_dynmap_file(info, share->state.state.data_file_length))
 
1445
      return(0);
 
1446
  }
 
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;
 
1450
  return(1);
 
1451
}
 
1452
 
 
1453
 
 
1454
void _mi_unmap_file(MI_INFO *info)
 
1455
{
 
1456
  VOID(my_munmap((char*) info->s->file_map, 
 
1457
                 (size_t) info->s->mmaped_length + MEMMAP_EXTRA_MARGIN));
 
1458
}
 
1459
 
 
1460
 
 
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,
 
1463
                                         uchar *header)
 
1464
{
 
1465
  header+= read_pack_length((uint) myisam->s->pack.version, header,
 
1466
                            &info->rec_len);
 
1467
  if (myisam->s->base.blobs)
 
1468
  {
 
1469
    header+= read_pack_length((uint) myisam->s->pack.version, header,
 
1470
                              &info->blob_len);
 
1471
    /* mi_alloc_rec_buff sets my_errno on error */
 
1472
    if (!(mi_alloc_rec_buff(myisam, info->blob_len,
 
1473
                            rec_buff_p)))
 
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;
 
1477
  }
 
1478
  return header;
 
1479
}
 
1480
 
 
1481
 
 
1482
static int _mi_read_mempack_record(MI_INFO *info, my_off_t filepos, uchar *buf)
 
1483
{
 
1484
  MI_BLOCK_INFO block_info;
 
1485
  MYISAM_SHARE *share=info->s;
 
1486
  uchar *pos;
 
1487
 
 
1488
  if (filepos == HA_OFFSET_ERROR)
 
1489
    return(-1);                 /* _search() didn't find record */
 
1490
 
 
1491
  if (!(pos= (uchar*) _mi_mempack_get_block_info(info, &info->bit_buff,
 
1492
                                                &block_info, &info->rec_buff,
 
1493
                                                (uchar*) share->file_map+
 
1494
                                                filepos)))
 
1495
    return(-1);
 
1496
  return(_mi_pack_rec_unpack(info, &info->bit_buff, buf,
 
1497
                                  pos, block_info.rec_len));
 
1498
}
 
1499
 
 
1500
 
 
1501
/*ARGSUSED*/
 
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)))
 
1506
{
 
1507
  MI_BLOCK_INFO block_info;
 
1508
  MYISAM_SHARE *share=info->s;
 
1509
  uchar *pos,*start;
 
1510
 
 
1511
  if (filepos >= share->state.state.data_file_length)
 
1512
  {
 
1513
    my_errno=HA_ERR_END_OF_FILE;
 
1514
    goto err;
 
1515
  }
 
1516
  if (!(pos= (uchar*) _mi_mempack_get_block_info(info, &info->bit_buff,
 
1517
                                                &block_info, &info->rec_buff,
 
1518
                                                (uchar*)
 
1519
                                                (start=share->file_map+
 
1520
                                                 filepos))))
 
1521
    goto err;
 
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;
 
1526
 
 
1527
  return (_mi_pack_rec_unpack(info, &info->bit_buff, buf,
 
1528
                                   pos, block_info.rec_len));
 
1529
 err:
 
1530
  return(my_errno);
 
1531
}
 
1532
 
 
1533
#endif /* HAVE_MMAP */
 
1534
 
 
1535
        /* Save length of row */
 
1536
 
 
1537
uint save_pack_length(uint version, uchar *block_buff, ulong length)
 
1538
{
 
1539
  if (length < 254)
 
1540
  {
 
1541
    *(uchar*) block_buff= (uchar) length;
 
1542
    return 1;
 
1543
  }
 
1544
  if (length <= 65535)
 
1545
  {
 
1546
    *(uchar*) block_buff=254;
 
1547
    int2store(block_buff+1,(uint) length);
 
1548
    return 3;
 
1549
  }
 
1550
  *(uchar*) block_buff=255;
 
1551
  if (version == 1) /* old format */
 
1552
  {
 
1553
    assert(length <= 0xFFFFFF);
 
1554
    int3store(block_buff + 1, (ulong) length);
 
1555
    return 4;
 
1556
  }
 
1557
  else
 
1558
  {
 
1559
    int4store(block_buff + 1, (ulong) length);
 
1560
    return 5;
 
1561
  }
 
1562
}
 
1563
 
 
1564
 
 
1565
uint read_pack_length(uint version, const uchar *buf, ulong *length)
 
1566
{
 
1567
  if (buf[0] < 254)
 
1568
  {
 
1569
    *length= buf[0];
 
1570
    return 1;
 
1571
  }
 
1572
  else if (buf[0] == 254)
 
1573
  {
 
1574
    *length= uint2korr(buf + 1);
 
1575
    return 3;
 
1576
  }
 
1577
  if (version == 1) /* old format */
 
1578
  {
 
1579
    *length= uint3korr(buf + 1);
 
1580
    return 4;
 
1581
  }
 
1582
  else
 
1583
  {
 
1584
    *length= uint4korr(buf + 1);
 
1585
    return 5;
 
1586
  }
 
1587
}
 
1588
 
 
1589
 
 
1590
uint calc_pack_length(uint version, ulong length)
 
1591
{
 
1592
  return (length < 254) ? 1 : (length < 65536) ? 3 : (version == 1) ? 4 : 5;
 
1593
}