Below is the list of changes that have just been committed into a local
4.0 repository of mydev. When mydev does a push these changes will
be propagated to the main repository and, within 24 hours after the
push, to the public repository.
For information on how to access the public repository
see http://dev.mysql.com/doc/mysql/en/in...urce-tree.html

ChangeSet
1.2063 05/03/11 21:17:20 ingo (AT) mysql (DOT) com +4 -0
Bug#8321 - myisampack bug in compression algorithm
This is the first of three changesets. It does not contain the bug fix.
It adds comments, trace and debug prints, a few coding style fixes,
small code reorderings to better show the relations of the statements,
some additional checks, and a new describe and check feature for
compressed data files.

myisam/myisampack.c
1.35 05/03/11 21:16:57 ingo (AT) mysql (DOT) com +867 -63
Bug#8321 - myisampack bug in compression algorithm
This is the first of three changesets. It does not contain the bug fix.
Added comments, trace and debug prints, a few coding style fixes,
small code reorderings to better show the relations of the statements,
and some additional checks.

myisam/myisamchk.c
1.116 05/03/11 21:16:57 ingo (AT) mysql (DOT) com +871 -0
Bug#8321 - myisampack bug in compression algorithm
This is the first of three changesets. It does not contain the bug fix.
Added a new describe and check feature for compressed data files.

myisam/mi_packrec.c
1.23 05/03/11 21:16:57 ingo (AT) mysql (DOT) com +1 -1
Bug#8321 - myisampack bug in compression algorithm
This is the first of three changesets. It does not contain the bug fix.
Fixed a comment.

include/my_base.h
1.42 05/03/11 21:16:57 ingo (AT) mysql (DOT) com +1 -0
Bug#8321 - myisampack bug in compression algorithm
This is the first of three changesets. It does not contain the bug fix.
Added a comment.

# This is a BitKeeper patch. What follows are the unified diffs for the
# set of deltas contained in the patch. The rest of the patch, the part
# that BitKeeper cares about, is below these diffs.
# User: ingo
# Host: chilla.local
# Root: /home/mydev/mysql-4.0-bug8321

--- 1.41/include/my_base.h Fri Dec 12 21:26:56 2003
+++ 1.42/include/my_base.h Fri Mar 11 21:16:57 2005
@@ -311,6 +311,7 @@
#define HA_STATE_ROW_CHANGED 1024 /* To invalide ROW cache */
#define HA_STATE_EXTEND_BLOCK 2048

+/* myisampack expects no more than 32 field types. */
enum en_fieldtype {
FIELD_LAST=-1,FIELD_NORMAL,FIELD_SKIP_ENDSPACE,FIELD_SKIP_PRES PACE,
FIELD_SKIP_ZERO,FIELD_BLOB,FIELD_CONSTANT,FIELD_IN TERVALL,FIELD_ZERO,

--- 1.22/myisam/mi_packrec.c Wed Sep 24 13:33:21 2003
+++ 1.23/myisam/mi_packrec.c Fri Mar 11 21:16:57 2005
@@ -406,7 +406,7 @@


/* Read record from datafile */
- /* Returns length of packed record, -1 if error */
+ /* Returns 0 on success or HA_ERR_WRONG_IN_RECORD or -1 on error */

int _mi_read_pack_record(MI_INFO *info, my_off_t filepos, byte *buf)
{

--- 1.115/myisam/myisamchk.c Tue Aug 31 18:27:56 2004
+++ 1.116/myisam/myisamchk.c Fri Mar 11 21:16:57 2005
@@ -20,6 +20,7 @@

#include <m_ctype.h>
#include <stdarg.h>
+#include <assert.h>
#include <my_getopt.h>
#ifdef HAVE_SYS_VADVICE_H
#include <sys/vadvise.h>
@@ -78,6 +79,7 @@
MI_KEYDEF *keyinfo,
my_off_t page,uchar *buff,uint sortkey,
File new_file, my_bool update_index);
+static void describe_compressed_data_file(MI_CHECK *param, MI_INFO *info);

MI_CHECK check_param;

@@ -1383,6 +1385,9 @@
start+=share->rec[field].length;
}
}
+ if ((param->testflag & T_EXTEND) &&
+ (share->options & HA_OPTION_COMPRESS_RECORD))
+ describe_compressed_data_file(param, info);
DBUG_VOID_RETURN;
} /* describe */

@@ -1721,3 +1726,869 @@
va_end(args);
DBUG_VOID_RETURN;
}
+
+
+/*
+ The following section is used to describe a compressed data file.
+*/
+
+#include <sys/types.h>
+#include <stdio.h>
+#include <errno.h>
+#include <string.h>
+
+static int verbosity;
+
+#define PRINT3(_arglist_) {if (verbosity >= 3) printf _arglist_;}
+#define PRINT4(_arglist_) {if (verbosity >= 4) printf _arglist_;}
+#ifdef EXTRA_DEBUG
+#define DBG5(_arglist_) {if (verbosity >= 5) printf _arglist_;}
+#else
+#define DBG5(_arglist_) {}
+#endif
+#define IS_OFFSET ((uint) 32768) /* Bit if offset or char in tree */
+
+typedef struct st_pack_header PACK_HEADER ;
+struct st_pack_header
+{
+ uchar magic[4];
+ uint header_length;
+ uint min_pack_length;
+ uint max_pack_length;
+ uint elements;
+ uint interval_length;
+ ushort decode_trees;
+ uchar ref_length;
+ uchar rec_reflength;
+ uchar filler[4];
+};
+
+typedef struct st_column_info COLUMN_INFO ;
+struct st_column_info
+{
+ uint column_no;
+ uint field_type;
+ uint pack_type;
+ uint min_zero_tail;
+ uint length_bits;
+ uint decode_tree_no;
+ MI_COLUMNDEF *coldef;
+};
+
+typedef struct st_decode_tree DECODE_TREE ;
+struct st_decode_tree
+{
+ uint tree_no;
+ uint have_column_values;
+ uint elements;
+ uint char_bits;
+ uint offset_bits;
+ uint value_buffer_length;
+ uint min_chr;
+ uint tree_length;
+ uint *packed_tree;
+ uchar *column_values;
+};
+
+typedef struct st_bit_buffer BIT_BUFFER ;
+struct st_bit_buffer
+{
+ FILE *fp; /* File pointer to read from. */
+ ulong byte_count; /* Number of bytes read from fp. */
+ uint bits; /* Number of valid bits in buffer. */
+ uchar buffer; /* Valid bits are high-aligned. */
+};
+
+#define init_bit_buffer(_f_,_b_) {(_b_)->fp= fp; (_b_)->byte_count= 0; \
+ (_b_)->bits= 0; (_b_)->buffer= 0;}
+/* ignore remaining bits in bit buffer. */
+#define flush_bit_buffer(_b_) {(_b_)->bits= 0;}
+
+
+/*
+ Convert a value into binary digits.
+
+ SYNOPSIS
+ bindigits()
+ value The value.
+ length The number of low order bits to convert.
+
+ DESCRIPTION
+ The result string is in static storage. It is reused on every call.
+ So you cannot use it twice in one expression.
+
+ RETURN
+ A pointer to a static NUL-terminated string.
+ */
+
+static char *bindigits(ulong value, uint bits)
+{
+ static char digits[72];
+ char *ptr= digits;
+ uint idx= bits;
+
+ DBUG_ASSERT(bits < sizeof(digits));
+ while (idx)
+ *(ptr++)= '0' + ((value >> (--idx)) & 1);
+ *ptr= '\0';
+ return digits;
+}
+
+
+/*
+ Get a value from a bit buffer which reads from a file.
+
+ SYNOPSIS
+ get_bits()
+ want_bits The number of bits for the value.
+ bit_buffer The bit buffer.
+
+ RETURN
+ The value made of the requested number of bits.
+*/
+
+static ulong get_bits(uint want_bits, BIT_BUFFER* bit_buffer)
+{
+ uint left_bits;
+ uint copy_bits;
+ ulong value;
+
+ DBG5(("want bits: %2u\n", want_bits));
+ DBUG_ASSERT(want_bits <= sizeof(ulong) * 8);
+ left_bits= want_bits;
+ value= 0;
+ do
+ {
+ if (! bit_buffer->bits)
+ {
+ bit_buffer->buffer= fgetc(bit_buffer->fp);
+ bit_buffer->bits= 8;
+ bit_buffer->byte_count++;
+ DBG5(("bit buffer I/O: 0x%02x bits: 8 bin: %s\n",
+ bit_buffer->buffer, bindigits(bit_buffer->buffer, 8)));
+ }
+ copy_bits= (left_bits < bit_buffer->bits) ? left_bits : bit_buffer->bits;
+ left_bits-= copy_bits;
+ value<<= copy_bits;
+ value|= bit_buffer->buffer >> (8 - copy_bits);
+ bit_buffer->buffer<<= copy_bits;
+ bit_buffer->bits-= copy_bits;
+ DBG5((left_bits ? "prelim value: 0x%08lx bits: %2u bin: %s\n" : "",
+ value, want_bits - left_bits,
+ bindigits(value, want_bits - left_bits)));
+ }
+ while (left_bits);
+ DBG5(("leave value: 0x%08lx bits: %2u bin: %s\n",
+ value, want_bits, bindigits(value, want_bits)));
+ DBG5(("leave buffer: 0x%02x bits: %2u bin: %s\n",
+ bit_buffer->buffer, bit_buffer->bits,
+ bindigits(bit_buffer->buffer >> (8 - bit_buffer->bits),
+ bit_buffer->bits)));
+ return(value);
+}
+
+
+/*
+ Get the number of the highest bit set in a value.
+
+ SYNOPSIS
+ max_bit()
+ value The value.
+
+ RETURN
+ The number of the highest bit set. The least order bit counts as 1.
+ A minimum of 1 is returned.
+*/
+
+static uint max_bit(uint value)
+{
+ uint power=1;
+
+ while ((value>>= 1))
+ power++;
+ return (power);
+}
+
+
+/*
+ Print a hexadecimal dump of a buffer.
+
+ SYNOPSIS
+ ihexdump()
+ buffer The buffer.
+ length The number of bytes to dump.
+
+ DESCRIPTION
+ Output goes to stdout. It begins and ends with a newline.
+ Each line contains the offset in the buffer of the first byte shown,
+ the hex values for 16 bytes and the character representation for the
+ 16 bytes. Non-printable chars are replaced by '~'.
+
+ RETURN
+ void
+ */
+
+static void ihexdump(uchar *buffer, uint length)
+{
+ uint idx= 0;
+ uint jdx= 0;
+
+ for (; idx < length; idx++)
+ {
+ if (idx % 16 == 0)
+ printf("\n0x%08x ", idx);
+ if (idx % 8 == 0)
+ printf(" ");
+ printf("%02x ", buffer[idx]);
+
+ if (idx % 16 == 15)
+ {
+ printf(" '");
+ for (; jdx <= idx; jdx++)
+ printf("%c", isprint(buffer[jdx]) ? buffer[jdx] : '~');
+ printf("'");
+ }
+ }
+ for (; idx % 16; idx++)
+ {
+ if (idx % 8 == 0)
+ printf(" ");
+ printf(" ");
+
+ if (idx % 16 == 15)
+ {
+ printf(" '");
+ for (; jdx < length; jdx++)
+ printf("%c", isprint(buffer[jdx]) ? buffer[jdx] : '~');
+ printf("'");
+ }
+ }
+ printf("\n");
+}
+
+
+/*
+ Decode values.
+
+ SYNOPSIS
+ decode_values()
+ length The number of values to decode.
+ dtp The decode tree to use.
+ bit_buffer The bit buffer to read from.
+
+ DESCRIPTION
+ This function does not store the decoded values.
+ Its purpose is to fetch the value codes from the file.
+ So it can be checked, if the length info is correct. A decoding error
+ should show up as a record length mismatch. It should interpret the
+ Huffman codes differently and as such most probably use different
+ code length.
+
+ RETURN
+ 0 OK
+ != 0 Error
+*/
+
+static int decode_values(ulong length, DECODE_TREE *dtp,
+ BIT_BUFFER *bit_buffer)
+{
+ ulong code;
+ uint bits;
+ uint idx;
+ uint value;
+
+ while (length--)
+ {
+ code= 0;
+ bits= 0;
+ idx= 0;
+ for (;
+ {
+ code<<= 1;
+ code|= get_bits(1, bit_buffer);
+ bits++;
+ DBG5(("code: 0x%08lx bits: %2u bin: %s\n",
+ code, bits, bindigits(code, bits)));
+ idx+= (uint) code & 1;
+ if (idx >= dtp->tree_length)
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "illegal tree offset: %u/%u\n", idx, dtp->tree_length);
+ return 1;
+ }
+ DBG5(("get real idx: 0x%04x\n", idx));
+ if (dtp->packed_tree[idx] & IS_OFFSET)
+ idx+= dtp->packed_tree[idx] & ~IS_OFFSET;
+ else
+ break; /* Hit a leaf. This contains the result value. */
+ DBG5(("new base idx: 0x%04x\n", idx));
+ }
+
+ value= dtp->packed_tree[idx];
+ PRINT4((dtp->have_column_values ?
+ "index: 0x%04x code: 0x%08lx bits: %2u bin: %s\n" :
+ "value: 0x%02x code: 0x%08lx bits: %2u bin: %s\n",
+ value, code, bits, bindigits(code, bits)));
+ if ((dtp->have_column_values && (value >= dtp->elements)) ||
+ (! dtp->have_column_values && (value > 255)))
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "illegal decoded value: 0x%04x/0x%04x\n", value ,
+ dtp->have_column_values ? dtp->elements : 0xff);
+ return 1;
+ }
+ if (feof(bit_buffer->fp) || ferror(bit_buffer->fp))
+ return 1;
+ }
+ return 0;
+}
+
+
+/*
+ Describe the contents of a compressed data file.
+
+ SYNOPSIS
+ describe_compressed_data_file()
+ param Check parameters.
+ info MI_INFO for an open MyISAM table.
+
+ RETURN
+ void
+*/
+
+static void describe_compressed_data_file(MI_CHECK *param, MI_INFO *info)
+{
+ uint col ;
+ uint idx ;
+ uint lgt ;
+ uint collen ;
+ uint decode_tree_no_bits;
+ ulong len_packlen;
+ ulong packreclen;
+ ulong tot_bloblen ;
+ ulong sum_bloblen ;
+ ulong bloblen ;
+ my_off_t record_count;
+ char number[64];
+ fpos_t rec_pos;
+ fpos_t data_pos;
+ MYISAM_SHARE *share= info->s;
+ FILE *fp ;
+ PACK_HEADER header_buffer ;
+ PACK_HEADER *header= &header_buffer ;
+ COLUMN_INFO *column_info_array= NULL;
+ COLUMN_INFO *cip;
+ COLUMN_INFO *end_cip;
+ DECODE_TREE *decode_tree_array= NULL;
+ DECODE_TREE *dtp;
+ DECODE_TREE *end_dtp;
+ BIT_BUFFER bit_buffer;
+ uchar *record;
+
+ verbosity= param->verbose;
+
+ /* Open data file. */
+ fp= fopen(share->data_file_name, "r");
+ if (! fp)
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "Cannot open '%s': %s\n",
+ share->data_file_name, strerror(errno));
+ return;
+ }
+ init_bit_buffer(fp, &bit_buffer);
+
+ /*
+ ------
+ Header
+ ------
+ */
+ printf("\n");
+ printf("\n");
+ printf("Compressed data file '%s'\n", share->data_file_name);
+ printf("\n");
+ DBG5(("=========================================== ===================\n"));
+ printf("Header. Offset %ld\n", ftell(fp));
+ /* Read header. */
+ if (fread(header, 1, sizeof(PACK_HEADER), fp) != sizeof(PACK_HEADER))
+ goto err;
+ /* Describe header. */
+ printf("header->magic 0x%02x%02x%02x%02x (%s)\n",
+ header->magic[0], header->magic[1],
+ header->magic[2], header->magic[3],
+ ((header->magic[0] == 0xfe) && (header->magic[1] == 0xfe) &&
+ (header->magic[2] == 0x08) && (header->magic[3] == 0x01)) ?
+ "OK" : "WRONG");
+ printf("header->header_length %u\n", header->header_length);
+ printf("header->min_pack_length %u\n", header->min_pack_length);
+ printf("header->max_pack_length %u\n", header->max_pack_length);
+ printf("header->elements %u\n", header->elements);
+ printf("header->interval_length %u\n", header->interval_length);
+ printf("header->decode_trees %u\n", header->decode_trees);
+ printf("header->ref_length %u\n", header->ref_length);
+ printf("header->rec_reflength %u\n", header->rec_reflength);
+ printf("header->filler 0x%02x%02x%02x%02x\n",
+ header->filler[0], header->filler[1],
+ header->filler[2], header->filler[3]);
+ decode_tree_no_bits= max_bit(header->decode_trees ?
+ header->decode_trees - 1 : 0);
+ printf("bits used for tree numbers %u\n", decode_tree_no_bits);
+
+ /*
+ -----------
+ Column info
+ -----------
+ */
+ printf("\n");
+ DBG5(("=========================================== ===================\n"));
+ printf("Column info. Offset %ld\n", ftell(fp));
+
+ /* Allocate the column info structs. */
+ if (! (column_info_array= (COLUMN_INFO*)
+ my_malloc(share->base.fields * sizeof(COLUMN_INFO),
+ MYF(MY_WME | MY_ZEROFILL))))
+ goto err;
+ /* Read and describe field info. */
+ end_cip= column_info_array + share->base.fields;
+ col= 0;
+ for (cip= column_info_array; cip < end_cip; cip++)
+ {
+ DBG5(("---\n"));
+ cip->column_no= ++col;
+ cip->field_type= get_bits(5, &bit_buffer);
+ cip->pack_type= get_bits(6, &bit_buffer);
+ if (cip->pack_type & PACK_TYPE_ZERO_FILL)
+ cip->min_zero_tail= get_bits(5, &bit_buffer);
+ else
+ cip->length_bits= get_bits(5, &bit_buffer);
+ cip->decode_tree_no= get_bits(decode_tree_no_bits, &bit_buffer) + 1;
+ cip->coldef= share->rec + col - 1;
+
+ printf("column: %2u type: %2u pack: %2u zero: %4u lbits: %2u "
+ "tree: %2u length: %4u\n", cip->column_no, cip->field_type,
+ cip->pack_type, cip->min_zero_tail, cip->length_bits,
+ cip->decode_tree_no, cip->coldef->length);
+ }
+ /* The remaining bits of the last byte are waste. */
+ flush_bit_buffer(&bit_buffer);
+
+ /*
+ ----------------
+ Decode tree info
+ ----------------
+ */
+ printf("\n");
+ DBG5(("=========================================== ===================\n"));
+ printf("Decode info. Offset %ld\n", ftell(fp));
+ /* Allocate the decode tree structs. */
+ if (! (decode_tree_array= (DECODE_TREE*)
+ my_malloc(header->decode_trees * sizeof(DECODE_TREE),
+ MYF(MY_WME | MY_ZEROFILL))))
+ goto err;
+ /* Read and describe decode tree info. */
+ end_dtp= decode_tree_array + header->decode_trees;
+ col= 0;
+ for (dtp= decode_tree_array; dtp < end_dtp; dtp++)
+ {
+ DBG5(("============================\n"));
+ dtp->tree_no= ++col;
+ /*
+ The trees contain decode information for either bytes or distinct
+ column values.
+ */
+ dtp->have_column_values= get_bits(1, &bit_buffer);
+ if (! dtp->have_column_values)
+ {
+ /* Compressed bytes. */
+ dtp->min_chr= get_bits(8, &bit_buffer);
+ dtp->elements= get_bits(9, &bit_buffer);
+ dtp->char_bits= get_bits(5, &bit_buffer);
+ dtp->offset_bits= get_bits(5, &bit_buffer);
+ }
+ else
+ {
+ /* Compressed distinct column values. */
+ dtp->elements= get_bits(15, &bit_buffer);
+ dtp->value_buffer_length= get_bits(16, &bit_buffer);
+ dtp->char_bits= get_bits(5, &bit_buffer);
+ dtp->offset_bits= get_bits(5, &bit_buffer);
+ }
+ printf("tree: %2u elements: %4u char_bits: %2u offset_bits: %2u "
+ "%s: %u\n", dtp->tree_no, dtp->elements, dtp->char_bits,
+ dtp->offset_bits, dtp->have_column_values ?
+ "value_buffer_length" : "min_chr", dtp->have_column_values ?
+ dtp->value_buffer_length : dtp->min_chr);
+
+ /*
+ The trees are arrays of pairs of numbers, which are either indexes
+ into the tree itself (tree nodes) or byte codes/column value indexes
+ (tree leafs).
+ */
+ dtp->tree_length= dtp->elements * 2 - 2;
+ if (! (dtp->packed_tree= (uint*) my_malloc(dtp->tree_length * sizeof(uint),
+ MYF(MY_WME))))
+ goto err;
+ for (idx= 0; idx < dtp->tree_length; idx++)
+ {
+ DBG5(("---\n"));
+ /*
+ One bit determines if we have nodes or leafs.
+ Both may be coded with different numbers of bits.
+ */
+ if (get_bits(1, &bit_buffer))
+ dtp->packed_tree[idx]= (get_bits(dtp->offset_bits, &bit_buffer) |
+ IS_OFFSET);
+ else
+ dtp->packed_tree[idx]= (get_bits(dtp->char_bits, &bit_buffer) +
+ dtp->min_chr);
+ PRINT4(("tree[0x%04x]: %s0x%04x \n", idx,
+ (dtp->packed_tree[idx] & IS_OFFSET) ? " -> " : "",
+ (dtp->packed_tree[idx] & IS_OFFSET) ?
+ dtp->packed_tree[idx] - IS_OFFSET + idx : dtp->packed_tree[idx]));
+ }
+ /* The remaining bits of the last byte are waste. */
+ flush_bit_buffer(&bit_buffer);
+
+ /* Read column values in case of distinct column value compression. */
+ if (dtp->have_column_values)
+ {
+ if (! (dtp->column_values= (uchar*) my_malloc(dtp->value_buffer_length,
+ MYF(MY_WME))))
+ goto err;
+ /* Read column values. */
+ for (idx= 0; idx < dtp->value_buffer_length; idx++)
+ {
+ dtp->column_values[idx]= get_bits(8, &bit_buffer);
+ PRINT4(("column_values[0x%04x]: 0x%02x \n",
+ idx, dtp->column_values[idx]));
+ }
+ }
+ }
+
+ /*
+ ------------
+ Data records
+ ------------
+ */
+ printf("\n");
+ DBG5(("=========================================== ===================\n"));
+ printf("Data records. Offset %ld\n", ftell(fp));
+ if (! (record= (uchar*) my_malloc(header->max_pack_length, MYF(MY_WME))))
+ goto err;
+
+ PRINT4(("===\n"));
+ record_count= 0;
+ while (! feof(fp) && ! ferror(fp))
+ {
+ fgetpos(fp, &rec_pos);
+ bit_buffer.byte_count= 0;
+
+ /*
+ Get the record length, and the total blob length.
+ Cannot use get_bits(16..) here, due to low-high byte order.
+ */
+ packreclen= get_bits(8, &bit_buffer);
+ if (packreclen > 253)
+ {
+ if (packreclen == 254)
+ packreclen= (get_bits(8, &bit_buffer) |
+ (get_bits(8, &bit_buffer) << 8));
+ else
+ packreclen= (get_bits(8, &bit_buffer) |
+ (get_bits(8, &bit_buffer) << 8) |
+ (get_bits(8, &bit_buffer) << 16) |
+ (get_bits(8, &bit_buffer) << 24));
+ }
+ tot_bloblen= 0;
+ if (share->base.blobs)
+ {
+ tot_bloblen= get_bits(8, &bit_buffer);
+ if (tot_bloblen > 253)
+ {
+ if (tot_bloblen == 254)
+ tot_bloblen= (get_bits(8, &bit_buffer) |
+ (get_bits(8, &bit_buffer) << 8));
+ else
+ tot_bloblen= (get_bits(8, &bit_buffer) |
+ (get_bits(8, &bit_buffer) << 8) |
+ (get_bits(8, &bit_buffer) << 16) |
+ (get_bits(8, &bit_buffer) << 24));
+ }
+ }
+ len_packlen= bit_buffer.byte_count;
+ sum_bloblen= 0;
+ if (packreclen > header->max_pack_length)
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "record too long %lu/%u\n",
+ packreclen, header->max_pack_length);
+ fsetpos(fp, &rec_pos);
+ fread(record, 1, 5, fp);
+ fprintf(stderr, "length bytes: 0x%02x 0x%02x 0x%02x 0x%02x 0x%02x\n",
+ record[0], record[1], record[2], record[3], record[4]);
+ break;
+ }
+
+ /* Dump the record contents. */
+ if (verbosity >= 5)
+ {
+ fgetpos(fp, &data_pos);
+ fsetpos(fp, &rec_pos);
+ if (fread(record, 1, len_packlen + packreclen, fp) !=
+ len_packlen + packreclen)
+ goto err;
+ ihexdump(record, packreclen);
+ fsetpos(fp, &data_pos);
+ printf("\n");
+ }
+
+ /* Get all column contents. */
+ for (cip= column_info_array; cip < end_cip; cip++)
+ {
+ PRINT4(("column: %2u type: %2u pack: %2u zero: %4u lbits: %2u "
+ "tree: %2u length: %4u\n", cip->column_no, cip->field_type,
+ cip->pack_type, cip->min_zero_tail, cip->length_bits,
+ cip->decode_tree_no, cip->coldef->length));
+ DBG5(("buffer: 0x%02x bits: %2u\n",
+ bit_buffer.buffer, bit_buffer.bits));
+
+ /* Check if the column contains spaces only. */
+ if (cip->pack_type & PACK_TYPE_SPACE_FIELDS)
+ {
+ if (get_bits(1, &bit_buffer))
+ {
+ PRINT4(("PACK_TYPE_SPACE_FIELDS spaces only, bits: 1\n---\n"));
+ continue;
+ }
+ PRINT4(("PACK_TYPE_SPACE_FIELDS not only spaces, bits: 1\n"));
+ }
+ collen= cip->coldef->length - cip->min_zero_tail;
+ dtp= decode_tree_array + cip->decode_tree_no - 1;
+
+ switch(cip->field_type) {
+ case FIELD_SKIP_ZERO:
+ /* Check if the column contains zeroes only. */
+ if (get_bits(1, &bit_buffer))
+ {
+ /* Yes, zeroes only. */
+ PRINT4(("FIELD_SKIP_ZERO zeroes only, bits: 1\n"));
+ break;
+ }
+ /* Not only zeroes. */
+ PRINT4(("FIELD_SKIP_ZERO not only zeroes, bits: 1\n"));
+ /* Fall through */
+
+ case FIELD_NORMAL:
+ PRINT4(("FIELD_NORMAL %u bytes\n", collen));
+ /* Decode all significant bytes. */
+ if (decode_values(collen, dtp, &bit_buffer))
+ goto err1;
+ break;
+
+ case FIELD_SKIP_ENDSPACE:
+ /* If not all trailing spaces are to be marked, check it. */
+ if (cip->pack_type & PACK_TYPE_SELECTED)
+ {
+ if (! (lgt= get_bits(1, &bit_buffer)))
+ {
+ PRINT4(("FIELD_SKIP_ENDSPACE not more than min_space, bits: 1\n"));
+ lgt= 0;
+ }
+ else
+ {
+ lgt= get_bits(cip->length_bits, &bit_buffer);
+ PRINT4(("FIELD_SKIP_ENDSPACE more than min_space, bits: 1\n"
+ "FIELD_SKIP_ENDSPACE skip %u/%u bytes, bits: %2u\n",
+ lgt, collen, cip->length_bits));
+ }
+ }
+ else
+ {
+ lgt= get_bits(cip->length_bits, &bit_buffer);
+ PRINT4(("FIELD_SKIP_ENDSPACE skip %u/%u bytes, bits: %2u\n",
+ lgt, collen, cip->length_bits));
+ }
+ if (lgt > collen)
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "too many skipped spaces %u column length %u\n",
+ lgt, collen);
+ goto err1;
+ }
+ /* Decode all significant bytes. */
+ PRINT4(("FIELD_SKIP_ENDSPACE %u bytes\n", collen - lgt));
+ if (decode_values(collen - lgt, dtp, &bit_buffer))
+ goto err1;
+ break;
+
+ case FIELD_SKIP_PRESPACE:
+ /* If not all trailing spaces are to be marked, check it. */
+ if (cip->pack_type & PACK_TYPE_SELECTED)
+ {
+ if (! (lgt= get_bits(1, &bit_buffer)))
+ {
+ PRINT4(("FIELD_SKIP_PRESPACE not more than min_space, bits: 1\n"));
+ lgt= 0;
+ }
+ else
+ {
+ lgt= get_bits(cip->length_bits, &bit_buffer);
+ PRINT4(("FIELD_SKIP_PRESPACE more than min_space, bits: 1\n"
+ "FIELD_SKIP_PRESPACE skip %u/%u bytes, bits: %2u\n",
+ lgt, collen, cip->length_bits));
+ }
+ }
+ else
+ {
+ lgt= get_bits(cip->length_bits, &bit_buffer);
+ PRINT4(("FIELD_SKIP_PRESPACE skip %u/%u bytes, bits: %2u\n",
+ lgt, collen, cip->length_bits));
+ }
+ if (lgt > collen)
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "too many skipped spaces %u column length %u\n",
+ lgt, collen);
+ goto err1;
+ }
+ /* Decode all significant bytes. */
+ PRINT4(("FIELD_SKIP_PRESPACE %u bytes\n", collen - lgt));
+ if (decode_values(collen - lgt, dtp, &bit_buffer))
+ goto err1;
+ break;
+
+ case FIELD_CONSTANT:
+ case FIELD_ZERO:
+ case FIELD_CHECK:
+ PRINT4(("FIELD_CONSTANT/ZERO/CHECK\n"));
+ break;
+
+ case FIELD_INTERVALL:
+ PRINT4(("FIELD_INTERVALL\n"));
+ /* Decode all significant bytes. */
+ if (decode_values(1, dtp, &bit_buffer))
+ goto err1;
+ break;
+
+ case FIELD_BLOB:
+ {
+ /* Empty blobs are encoded with a single 1 bit. */
+ if (get_bits(1, &bit_buffer))
+ {
+ /* Yes, empty blob. */
+ PRINT4(("FIELD_BLOB empty, bits: 1\n"));
+ break;
+ }
+ PRINT4(("FIELD_BLOB not empty, bits: 1\n"));
+ /* Get the blob length. */
+ bloblen= get_bits(cip->length_bits, &bit_buffer);
+ if (bloblen > tot_bloblen)
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "blob too long %lu total blob length %lu\n",
+ bloblen, tot_bloblen);
+ goto err1;
+ }
+ sum_bloblen+= bloblen;
+ if (sum_bloblen > tot_bloblen)
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "blob too long %lu sum %lu total blob length %lu\n",
+ bloblen, sum_bloblen, tot_bloblen);
+ goto err1;
+ }
+ PRINT4(("FIELD_BLOB %lu bytes, bits: %2u\n",
+ bloblen, cip->length_bits));
+ /* Decode all significant bytes. */
+ if (decode_values(bloblen, dtp, &bit_buffer))
+ goto err1;
+ break;
+ }
+
+ case FIELD_VARCHAR:
+ {
+ /* Empty blobs are encoded with a single 1 bit. */
+ if (get_bits(1, &bit_buffer))
+ {
+ /* Yes, empty varchar. */
+ PRINT4(("FIELD_VARCHAR empty, bits: 1\n"));
+ break;
+ }
+ PRINT4(("FIELD_VARCHAR not empty, bits: 1\n"));
+ /* Get the varchar length. */
+ lgt= get_bits(cip->length_bits, &bit_buffer);
+ if (lgt > collen)
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "varchar too long %u column length %u\n",
+ lgt, collen);
+ goto err1;
+ }
+ PRINT4(("FIELD_VARCHAR %u bytes, bits: %2u\n",
+ lgt, cip->length_bits));
+ /* Decode all significant bytes. */
+ if (decode_values(lgt, dtp, &bit_buffer))
+ goto err1;
+ break;
+ }
+
+ case FIELD_LAST:
+ abort(); /* Impossible */
+ }
+ /*end switch*/
+ PRINT4(("---\n"));
+ }
+ /*end for cip < end_cip*/
+ /* The remaining bits of the last byte are waste. */
+ flush_bit_buffer(&bit_buffer);
+
+ if (bit_buffer.byte_count - len_packlen != packreclen)
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "record %lu length mismatch, read %lu, header says %lu\n",
+ (ulong) record_count, bit_buffer.byte_count - len_packlen,
+ packreclen);
+ break;
+ }
+ PRINT3(("record: %lu length: %lu blob-length: %lu length-bytes: %lu\n",
+ (ulong) record_count, packreclen, tot_bloblen, len_packlen));
+ PRINT4(("===\n"));
+
+ record_count++;
+ if ((param->testflag & T_WRITE_LOOP) && (verbosity <= 2) &&
+ (record_count % WRITE_COUNT == 0))
+ {
+ printf("%lu\r", (ulong) record_count);
+ VOID(fflush(stdout));
+ }
+ }
+ /*end while !eof*/
+
+err1:
+ VOID(longlong2str((longlong) record_count, number, 10));
+ printf("read %s records.\n", number);
+ goto end;
+
+err:
+ VOID(fflush(stdout));
+ if (ferror(fp))
+ fprintf(stderr, "Cannot read '%s': %s\n",
+ share->data_file_name, strerror(errno));
+ if (feof(fp))
+ fprintf(stderr , "File too short '%s'\n", share->data_file_name);
+end:
+ fclose(fp);
+
+ if (decode_tree_array)
+ {
+ end_dtp= decode_tree_array + header->decode_trees; /*Please the compiler*/
+ for (dtp= decode_tree_array; dtp < end_dtp; dtp++)
+ {
+ my_free((char*) dtp->packed_tree, MYF(MY_ALLOW_ZERO_PTR));
+ my_free((char*) dtp->column_values, MYF(MY_ALLOW_ZERO_PTR));
+ }
+ my_free((char*) decode_tree_array, MYF(0));
+ }
+ my_free((char*) column_info_array, MYF(MY_ALLOW_ZERO_PTR));
+}
+

--- 1.34/myisam/myisampack.c Wed Oct 27 21:51:24 2004
+++ 1.35/myisam/myisampack.c Fri Mar 11 21:16:57 2005
@@ -31,6 +31,7 @@
#define __GNU_LIBRARY__ /* Skip warnings in getopt.h */
#endif
#include <my_getopt.h>
+#include <assert.h>

#if INT_MAX > 32767
#define BITS_SAVED 32
@@ -38,6 +39,16 @@
#define BITS_SAVED 16
#endif

+/* Provide verbose listing and debugging for the compression process. */
+#define PRINT2(_arglist_) {if (verbose >= 2) printf _arglist_;}
+#define PRINT3(_arglist_) {if (verbose >= 3) printf _arglist_;}
+#define PRINT4(_arglist_) {if (verbose >= 4) printf _arglist_;}
+#ifdef EXTRA_DEBUG
+#define DBG5(_arglist_) {if (verbose >= 5) printf _arglist_;}
+#else
+#define DBG5(_arglist_) {}
+#endif
+
#define IS_OFFSET ((uint) 32768) /* Bit if offset or char in tree */
#define HEAD_LENGTH 32
#define ALLOWED_JOIN_DIFF 256 /* Diff allowed to join trees */
@@ -50,8 +61,8 @@
File file;
char *buffer,*pos,*end;
my_off_t pos_in_file;
- int bits;
- uint byte;
+ int bits; /* The number of bits free in 'byte'. */
+ uint byte; /* Up to BITS_SAVED bits are collected here. */
};

struct st_huff_tree;
@@ -68,13 +79,17 @@
my_off_t end_space[8];
my_off_t pre_space[8];
my_off_t tot_end_space,tot_pre_space,zero_fields,empty_fiel ds,bytes_packed;
- TREE int_tree;
- byte *tree_buff;
- byte *tree_pos;
+ TREE int_tree; /* Tree for detecting distinct column values. */
+ byte *tree_buff; /* About 8KB column values, 'field_length' each. */
+ byte *tree_pos; /* Points to end of column values in 'tree_buff'. */
} HUFF_COUNTS;

typedef struct st_huff_element HUFF_ELEMENT;

+/*
+ WARNING: It is crucial for the optimizations in calc_packed_length()
+ that 'count' is the first element of 'HUFF_ELEMENT'.
+*/
struct st_huff_element {
my_off_t count;
union un_element {
@@ -324,7 +339,7 @@
}
break;
case 'v':
- verbose= 1;
+ verbose++; /* Allow for selecting the level of verbosity. */
silent= 0;
break;
case '#':
@@ -525,6 +540,10 @@
trees=fields=share->base.fields;
huff_counts=init_huff_count(isam_file,mrg->records);
QUICK_SAFEMALLOC;
+
+ /*
+ Read the whole data file(s) for statistics.
+ */
if (write_loop || verbose)
printf("- Calculating statistics\n");
if (get_statistic(mrg,huff_counts))
@@ -535,27 +554,71 @@
old_length+= (mrg->file[i]->s->state.state.data_file_length -
mrg->file[i]->s->state.state.empty);

+ /*
+ Create a global priority queue in preparation for making
+ temoprary Huffman trees.
+ */
if (init_queue(&queue,256,0,0,compare_huff_elements,0 ))
goto err;
+
+ /*
+ Check each column if we should use pre-space-compress, end-space-
+ compress, empty-field-compress or zero-field-compress.
+ */
check_counts(huff_counts,fields,mrg->records);
+
+ /*
+ Build a Huffman tree for each column.
+ */
huff_trees=make_huff_trees(huff_counts,trees);
+
+ /*
+ If the packed lengths of combined columns is less then the sum of
+ the non-combined columns, then create common Huffman trees for them.
+ We do this only for byte compressed columns, not for distinct values
+ compressed columns.
+ */
if ((int) (used_trees=join_same_trees(huff_counts,trees)) < 0)
goto err;
+
+ /*
+ Assign codes to all byte or column values.
+ */
if (make_huff_decode_table(huff_trees,fields))
goto err;

+ /* Prepare a file buffer. */
init_file_buffer(new_file,0);
+
+ /*
+ Reserve space in the target file for the fixed compressed file header.
+ */
file_buffer.pos_in_file=HEAD_LENGTH;
if (! test_only)
VOID(my_seek(new_file,file_buffer.pos_in_file,MY_S EEK_SET,MYF(0)));

+ /*
+ Write field infos: field type, pack type, length bits, tree number.
+ */
write_field_info(huff_counts,fields,used_trees);
+
+ /*
+ Write decode trees.
+ */
if (!(tot_elements=write_huff_tree(huff_trees,trees)) )
goto err;
+
+ /*
+ Calculate the total length of the compression info header.
+ This includes the fixed compressed file header, the column compression
+ type descriptions, and the decode trees.
+ */
header_length=(uint) file_buffer.pos_in_file+
(uint) (file_buffer.pos-file_buffer.buffer);

- /* Compress file */
+ /*
+ Compress the source file into the target file.
+ */
if (write_loop || verbose)
printf("- Compressing file\n");
error=compress_isam_file(mrg,huff_counts);
@@ -567,16 +630,24 @@
error=my_write(file_buffer.file,buff,sizeof(buff),
MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)) != 0;
}
+
+ /*
+ Write the fixed compressed file header.
+ */
if (!error)
error=write_header(mrg,header_length,used_trees,to t_elements,
new_length);
+
+ /* Flush the file buffer. */
end_file_buffer();

+ /* Display statistics. */
if (verbose && mrg->records)
printf("Min record length: %6d Max length: %6d Mean total length: %6ld\n",
mrg->min_pack_length,mrg->max_pack_length,
(ulong) (new_length/mrg->records));

+ /* Close source and target file. */
if (!test_only)
{
error|=my_close(new_file,MYF(MY_WME));
@@ -587,6 +658,7 @@
}
}

+ /* Cleanup. */
free_counts_and_tree_and_queue(huff_trees,trees,hu ff_counts,fields);
if (! test_only && ! error)
{
@@ -676,6 +748,12 @@
(type == FIELD_NORMAL ||
type == FIELD_SKIP_ZERO))
count[i].max_zero_fill= count[i].field_length;
+ /*
+ For every column initialize a tree, which is used to detect distinct
+ column values. 'int_tree' works together with 'tree_buff' and
+ 'tree_pos'. It's keys are implemented by pointers into 'tree_buff'.
+ This is accomplished by '-1' as the element size.
+ */
init_tree(&count[i].int_tree,0,0,-1,(qsort_cmp2) compare_tree,0,NULL,NULL);
if (records && type != FIELD_BLOB && type != FIELD_VARCHAR)
count[i].tree_pos=count[i].tree_buff =
@@ -732,6 +810,9 @@
byte *record,*pos,*next_pos,*end_pos,*start_pos;
ha_rows record_count;
my_bool static_row_size;
+ uint idx;
+ my_off_t total_count;
+ char number[64];
HUFF_COUNTS *count,*end_count;
TREE_ELEMENT *element;
DBUG_ENTER("get_statistic");
@@ -759,10 +840,13 @@
ulong tot_blob_length=0;
if (! error)
{
+ /* glob_crc is a checksum over all bytes of all records. */
if (static_row_size)
glob_crc+=mi_static_checksum(mrg->file[0],record);
else
glob_crc+=mi_checksum(mrg->file[0],record);
+
+ /* Count the incidence of values separately for every column. */
for (pos=record,count=huff_counts ;
count < end_count ;
count++,
@@ -770,7 +854,26 @@
{
next_pos=end_pos=(start_pos=pos)+count->field_length;

- /* Put value in tree if there is room for it */
+ /*
+ Put the whole column value in a tree if there is room for it.
+ 'int_tree' is used to quickly check for duplicate values.
+ 'tree_buff' collects as many distinct column values as
+ possible. If the field length is > 1, it is about 8K, else 2
+ bytes. Each value is 'field_length' bytes big. An 'int' column
+ (4 bytes) will allow for about 2000 distinct values. If there
+ are more, we give up with this tree. BLOBs and VARCHARs do not
+ have a tree_buff (assumed to be too big). For the special case
+ of field length == 1, we handle only the case that there is
+ only one distinct value in the table(s). Otherwise, we can
+ have a maximum of 256 distinct values. This is then handled by
+ the normal Huffman tree build.
+
+ WARNING: At first, we insert a pointer into the record buffer
+ as the key for the tree. If we got a new distinct value, which
+ is really inserted into the tree, instead of being counted
+ only, we will copy the column value from the record buffer to
+ 'tree_buff' and adjust the key pointer of the tree accordingly.
+ */
if (count->tree_buff)
{
global_count=count;
@@ -787,10 +890,17 @@
}
else
{
+ /*
+ If tree_insert() succeeds, it either creates a new element
+ or increments the counter of an existing element.
+ */
if (element->count == 1)
- { /* New element */
+ {
+ /* Copy the new column value into 'tree_buff'. */
memcpy(count->tree_pos,pos,(size_t) count->field_length);
+ /* Adjust the key pointer in the tree. */
tree_set_pointer(element,count->tree_pos);
+ /* Point behind the last column value so far. */
count->tree_pos+=count->field_length;
}
}
@@ -800,15 +910,21 @@
if (count->field_type == FIELD_NORMAL ||
count->field_type == FIELD_SKIP_ENDSPACE)
{
+ /* Ignore trailing space. */
for ( ; end_pos > pos ; end_pos--)
if (end_pos[-1] != ' ')
break;
+ /* Empty fields are just counted. Go to the next record. */
if (end_pos == pos)
{
count->empty_fields++;
count->max_zero_fill=0;
continue;
}
+ /*
+ Count the total of all trailing spaces and the number of
+ short trailing spaces. Remember the longest trailing space.
+ */
length= (uint) (next_pos-end_pos);
count->tot_end_space+=length;
if (length < 8)
@@ -816,18 +932,25 @@
if (count->max_end_space < length)
count->max_end_space = length;
}
+
if (count->field_type == FIELD_NORMAL ||
count->field_type == FIELD_SKIP_PRESPACE)
{
+ /* Ignore leading space. */
for (pos=start_pos; pos < end_pos ; pos++)
if (pos[0] != ' ')
break;
+ /* Empty fields are just counted. Go to the next record. */
if (end_pos == pos)
{
count->empty_fields++;
count->max_zero_fill=0;
continue;
}
+ /*
+ Count the total of all leading spaces and the number of
+ short leading spaces. Remember the longest leading space.
+ */
length= (uint) (pos-start_pos);
count->tot_pre_space+=length;
if (length < 8)
@@ -835,6 +958,8 @@
if (count->max_pre_space < length)
count->max_pre_space = length;
}
+
+ /* Calculate pos, end_pos, and max_length for variable length fields. */
if (count->field_type == FIELD_BLOB)
{
uint field_length=count->field_length -mi_portable_sizeof_char_ptr;
@@ -851,27 +976,46 @@
end_pos=start_pos+length;
set_if_bigger(count->max_length,length);
}
+
+ /* Evaluate 'max_zero_fill' for short fields. */
if (count->field_length <= 8 &&
(count->field_type == FIELD_NORMAL ||
count->field_type == FIELD_SKIP_ZERO))
{
uint i;
+ /* Zero fields are just counted. Go to the next record. */
if (!memcmp((byte*) start_pos,zero_string,count->field_length))
{
count->zero_fields++;
continue;
}
+ /*
+ max_zero_fill starts with field_length. It is decreased every
+ time a shorter "zero trailer" is found. It is set to zero when
+ an empty field is found (see above). This suggests that the
+ variable should be called 'min_zero_fill'.
+ */
for (i =0 ; i < count->max_zero_fill && ! end_pos[-1 - (int) i] ;
i++) ;
if (i < count->max_zero_fill)
count->max_zero_fill=i;
}
+
+ /* Ignore zero fields and check fields. */
if (count->field_type == FIELD_ZERO ||
count->field_type == FIELD_CHECK)
continue;
+
+ /*
+ Count the incidence of every byte value in the
+ significant field value.
+ */
for ( ; pos < end_pos ; pos++)
count->counts[(uchar) *pos]++;
+
+ /* Step to next field. */
}
+
if (tot_blob_length > max_blob_length)
max_blob_length=tot_blob_length;
record_count++;
@@ -885,11 +1029,41 @@
fprintf(stderr,"Got error %d while reading rows",error);
break;
}
+
+ /* Step to next record. */
}
if (write_loop)
{
printf(" \r"); VOID(fflush(stdout));
}
+
+ if (verbose >= 2)
+ {
+ printf("Found the number of incidents of the byte codes:\n");
+ for (count= huff_counts ; count < end_count; count++)
+ {
+ printf("column %u\n", count - huff_counts);
+ if (count->tree_buff)
+ printf("number of distinct values: %u\n",
+ (count->tree_pos - count->tree_buff) / count->field_length);
+ total_count= 0;
+ for (idx= 0; idx < 256; idx++)
+ {
+ if (count->counts[idx])
+ {
+ total_count+= count->counts[idx];
+ VOID(longlong2str((longlong) count->counts[idx], number, 10));
+ printf("counts[0x%02x]: %12s\n", idx, number);
+ }
+ }
+ if (total_count)
+ {
+ VOID(longlong2str((longlong) total_count, number, 10));
+ printf("total %12s\n", number);
+ }
+ }
+ }
+
mrg->records=record_count;
mrg->max_blob_length=max_blob_length;
my_afree((gptr) record);
@@ -938,9 +1112,14 @@
huff_counts->field_type=FIELD_NORMAL;
huff_counts->pack_type=0;

+ /* Check for zero-filled records (in this column), or zero records. */
if (huff_counts->zero_fields || ! records)
{
my_off_t old_space_count;
+ /*
+ If there are only zero filled records (in this column),
+ or no records at all, we are done.
+ */
if (huff_counts->zero_fields == records)
{
huff_counts->field_type= FIELD_ZERO;
@@ -948,14 +1127,22 @@
huff_counts->counts[0]=0;
goto found_pack;
}
+ /* Remeber the number of significant spaces. */
old_space_count=huff_counts->counts[' '];
- huff_counts->counts[' ']+=huff_counts->tot_end_space+
- huff_counts->tot_pre_space +
- huff_counts->empty_fields * huff_counts->field_length;
+ /* Add all leading and trailing spaces. */
+ huff_counts->counts[' ']+= (huff_counts->tot_end_space +
+ huff_counts->tot_pre_space +
+ huff_counts->empty_fields *
+ huff_counts->field_length);
+ /* Check, what the compressed length of this would be. */
old_length=calc_packed_length(huff_counts,0)+recor ds/8;
- length=huff_counts->zero_fields*huff_counts->field_length;
- huff_counts->counts[0]+=length;
+ /* Get the number of zero bytes. */
+ length= huff_counts->zero_fields * huff_counts->field_length;
+ /* Add it to the counts. */
+ huff_counts->counts[0]+= length;
+ /* Check, what the compressed length of this would be. */
new_length=calc_packed_length(huff_counts,0);
+ /* If the compression without the zeroes would be shorter, we are done. */
if (old_length < new_length && huff_counts->field_length > 1)
{
huff_counts->field_type=FIELD_SKIP_ZERO;
@@ -963,9 +1150,16 @@
huff_counts->bytes_packed=old_length- records/8;
goto found_pack;
}
- huff_counts->counts[' ']=old_space_count;
+ /* Remove the insignificant spaces, but keep the zeroes. */
+ huff_counts->counts[' ']= old_space_count;
}
+ /* Check, what the compressed length of this column would be. */
huff_counts->bytes_packed=calc_packed_length(huff_counts,0);
+
+ /*
+ If there are enough empty records (in this column),
+ treating them specially may pay off.
+ */
if (huff_counts->empty_fields)
{
if (huff_counts->field_length > 2 &&
@@ -997,6 +1191,11 @@
}
}
}
+
+ /*
+ If there are enough trailing spaces (in this column),
+ treating them specially may pay off.
+ */
if (huff_counts->tot_end_space)
{
huff_counts->counts[' ']+=huff_counts->tot_pre_space;
@@ -1006,6 +1205,11 @@
goto found_pack;
huff_counts->counts[' ']-=huff_counts->tot_pre_space;
}
+
+ /*
+ If there are enough leading spaces (in this column),
+ treating them specially may pay off.
+ */
if (huff_counts->tot_pre_space)
{
if (test_space_compress(huff_counts,records,huff_coun ts->max_pre_space,
@@ -1164,8 +1368,24 @@
DBUG_RETURN(huff_tree);
}

- /* Update huff_tree according to huff_counts->counts or
- huff_counts->tree_buff */
+/*
+ Update huff_tree.
+
+ SYNOPSIS
+ make_huff_tree()
+ huff_tree The Huffman tree.
+ huff_counts The counts.
+
+ DESCRIPTION
+ Update huff_tree according to huff_counts->counts or
+ huff_counts->tree_buff. tree_buff, if non-NULL contains up to 8KB of
+ distinct column values. In that case, whole values can be Huffman
+ encoded instead of single bytes.
+
+ RETURN
+ 0 OK
+ != 0 Error
+*/

static int make_huff_tree(HUFF_TREE *huff_tree, HUFF_COUNTS *huff_counts)
{
@@ -1176,12 +1396,14 @@
first=last=0;
if (huff_counts->tree_buff)
{
+ /* Calculate the number of distinct values in tree_buff. */
found= (uint) (huff_counts->tree_pos - huff_counts->tree_buff) /
huff_counts->field_length;
first=0; last=found-1;
}
else
{
+ /* Count the number of byte codes found in the column. */
for (i=found=0 ; i < 256 ; i++)
{
if (huff_counts->counts[i])
@@ -1195,6 +1417,7 @@
found=2;
}

+ /* When using 'tree_buff' we can have more that 256 values. */
if (queue.max_elements < found)
{
delete_queue(&queue);
@@ -1202,6 +1425,7 @@
return -1;
}

+ /* Allocate or reallocate an element buffer for the Huffman tree. */
if (!huff_tree->element_buffer)
{
if (!(huff_tree->element_buffer=
@@ -1229,15 +1453,25 @@
if (huff_counts->tree_buff)
{
huff_tree->elements=0;
- tree_walk(&huff_counts->int_tree,
- (int (*)(void*, element_count,void*)) save_counts_in_queue,
- (gptr) huff_tree, left_root_right);
huff_tree->tree_pack_length=(1+15+16+5+5+
(huff_tree->char_bits+1)*found+
(huff_tree->offset_bits+1)*
(found-2)+7)/8 +
(uint) (huff_tree->counts->tree_pos-
huff_tree->counts->tree_buff);
+ /*
+ Put a HUFF_ELEMENT into the queue for every distinct column value.
+
+ tree_walk() calls save_counts_in_queue() for every element in
+ 'int_tree'. This takes elements from the target trees element
+ buffer and places references to them into the buffer of the
+ priority queue. We insert in column value order, but the order is
+ in fact irrelevant here. We will establish the correct order
+ later.
+ */
+ tree_walk(&huff_counts->int_tree,
+ (int (*)(void*, element_count,void*)) save_counts_in_queue,
+ (gptr) huff_tree, left_root_right);
}
else
{
@@ -1246,7 +1480,15 @@
(huff_tree->char_bits+1)*found+
(huff_tree->offset_bits+1)*
(found-2)+7)/8;
+ /*
+ Put a HUFF_ELEMENT into the queue for every byte code found in the column.

+ The elements are taken from the target trees element buffer.
+ Instead of using queue_insert(), we just place references to the
+ elements into the buffer of the priority queue. We insert in byte
+ value order, but the order is in fact irrelevant here. We will
+ establish the correct order later.
+ */
for (i=first, found=0 ; i <= last ; i++)
{
if (huff_counts->counts[i])
@@ -1258,8 +1500,13 @@
queue.root[found]=(byte*) new_huff_el;
}
}
+ /*
+ If there is only a single byte value in this field in all records,
+ add a second element with zero incidence. This is required to enter
+ the loop, which builds the Huffman tree.
+ */
while (found < 2)
- { /* Our huff_trees request at least 2 elements */
+ {
new_huff_el=huff_tree->element_buffer+(found++);
new_huff_el->count=0;
new_huff_el->a.leaf.null=0;
@@ -1270,21 +1517,53 @@
queue.root[found]=(byte*) new_huff_el;
}
}
+
+ /* Make a queue from the queue buffer. */
queue.elements=found;

+ /*
+ Make a priority queue from the queue. Construct its index so that we
+ have a partially ordered tree.
+ */
for (i=found/2 ; i > 0 ; i--)
_downheap(&queue,i);
+
+ /* The Huffman algorithm. */
bytes_packed=0; bits_packed=0;
for (i=1 ; i < found ; i++)
{
- a=(HUFF_ELEMENT*) queue_remove(&queue,0);
- b=(HUFF_ELEMENT*) queue.root[1];
- new_huff_el=huff_tree->element_buffer+found+i;
- new_huff_el->count=a->count+b->count;
- bits_packed+=(uint) (new_huff_el->count & 7);
- bytes_packed+=new_huff_el->count/8;
- new_huff_el->a.nod.left=a; /* lesser in left */
- new_huff_el->a.nod.right=b;
+ /*
+ Pop the top element from the queue (the one with the least incidence).
+ Popping from a priority queue includes a re-ordering of the queue,
+ to get the next least incidence element to the top.
+ */
+ a= (HUFF_ELEMENT*) queue_remove(&queue, 0);
+ /*
+ Copy the next least incidence element. The queue implementation
+ reserves root[0] for temporary purposes. root[1] is the top.
+ */
+ b= (HUFF_ELEMENT*) queue.root[1];
+ /* Get a new element from the element buffer. */
+ new_huff_el= huff_tree->element_buffer + found + i;
+ /* The new element gets the sum of the two least incidence elements. */
+ new_huff_el->count= a->count + b->count;
+ /*
+ The Huffman algorithm assigns another bit to the code for a byte
+ every time that bytes incidence is combined (directly or indirectly)
+ to a new element as one of the two least incidence elements.
+ This means that one more bit per incidence of that byte is required
+ in the resulting file. So we add the new combined incidence as the
+ number of bits by which the result grows.
+ */
+ bits_packed+= (uint) (new_huff_el->count & 7);
+ bytes_packed+= new_huff_el->count / 8;
+ /* The new element points to its children, lesser in left. */
+ new_huff_el->a.nod.left= a;
+ new_huff_el->a.nod.right= b;
+ /*
+ Replace the copied top element by the new element and re-order the
+ queue.
+ */
queue.root[1]=(byte*) new_huff_el;
queue_replaced(&queue);
}
@@ -1303,7 +1582,26 @@
return 0;
}

- /* Used by make_huff_tree to save intervall-counts in queue */
+/*
+ Organize distinct column values and their incidences into a priority queue.
+
+ SYNOPSIS
+ save_counts_in_queue()
+ key The column value.
+ count The incidence of this value.
+ tree The Huffman tree to be built later.
+
+ DESCRIPTION
+ We use the element buffer of the targeted tree. The distinct column
+ values are organized in a priority queue first. The Huffman
+ algorithm will later organize the elements into a Huffman tree. For
+ the time being, we just place references to the elements into the
+ queue buffer. The buffer will later be organized into a priority
+ queue.
+
+ RETURN
+ 0
+ */

static int save_counts_in_queue(byte *key, element_count count,
HUFF_TREE *tree)
@@ -1320,8 +1618,23 @@
}


- /* Calculate length of file if given counts should be used */
- /* Its actually a faster version of make_huff_tree */
+/*
+ Calculate length of file if given counts should be used.
+
+ SYNOPSIS
+ calc_packed_length()
+ huff_counts The counts for a column of the table(s).
+ add_tree_lenght If the decode tree length should be added.
+
+ DESCRIPTION
+ We need to follow the Huffman algorithm until we know, how many bits
+ are required for each byte code. But we do not need the resulting
+ Huffman tree. Hence, we can leave out some steps which are essential
+ in make_huff_tree().
+
+ RETURN
+ Number of bytes required to compress this table column.
+*/

static my_off_t calc_packed_length(HUFF_COUNTS *huff_counts,
uint add_tree_lenght)
@@ -1331,6 +1644,20 @@
HUFF_ELEMENT element_buffer[256];
DBUG_ENTER("calc_packed_length");

+ /*
+ Instead of placing HUFF_ELEMENTs into the queue, we just insert
+ references to the counts of all byte codes which appeared in this
+ table column. WARNING: This is **** (censored). It works, because
+ HUFF_ELEMENT has the incidence count at its beginning. Regardless,
+ if the queue array contains references to counts of type my_off_t or
+ references to HUFF_ELEMENT which has the count of type my_off_t at
+ its beginning, it always points to a count of the same type.
+
+ Instead of using queue_insert(), we just copy the references into
+ the buffer of the priority queue. We insert in byte value order, but
+ the order is in fact irrelevant here. We will establish the correct
+ order later.
+ */
first=last=0;
for (i=found=0 ; i < 256 ; i++)
{
@@ -1339,32 +1666,77 @@
if (! found++)
first=i;
last=i;
+ /* We start with root[1], which is the queues top element. */
queue.root[found]=(byte*) &huff_counts->counts[i];
}
}
if (!found)
DBUG_RETURN(0); /* Empty tree */
+ /*
+ If there is only a single byte value in this field in all records,
+ add a second element with zero incidence. This is required to enter
+ the loop, which follows the Huffman algorithm.
+ */
if (found < 2)
queue.root[++found]=(byte*) &huff_counts->counts[last ? 0 : 1];

+ /* Make a queue from the queue buffer. */
queue.elements=found;

bytes_packed=0; bits_packed=0;
+ /* Add the length of the coding table, which would become part of the file. */
if (add_tree_lenght)
bytes_packed=(8+9+5+5+(max_bit(last-first)+1)*found+
(max_bit(found-1)+1+1)*(found-2) +7)/8;
+
+ /*
+ Make a priority queue from the queue. Construct its index so that we
+ have a partially ordered tree.
+ */
for (i=(found+1)/2 ; i > 0 ; i--)
_downheap(&queue,i);
+
+ /* The Huffman algorithm. */
for (i=0 ; i < found-1 ; i++)
{
HUFF_ELEMENT *a,*b,*new_huff_el;
- a=(HUFF_ELEMENT*) queue_remove(&queue,0);
- b=(HUFF_ELEMENT*) queue.root[1];
- new_huff_el=element_buffer+i;
- new_huff_el->count=a->count+b->count;
- bits_packed+=(uint) (new_huff_el->count & 7);
- bytes_packed+=new_huff_el->count/8;
- queue.root[1]=(byte*) new_huff_el;
+ /*
+ Pop the top element from the queue (the one with the least incidence).
+ Popping from a priority queue includes a re-ordering of the queue,
+ to get the next least incidence element to the top.
+ */
+ a= (HUFF_ELEMENT*) queue_remove(&queue, 0);
+ /*
+ Copy the next least incidence element. The queue implementation
+ reserves root[0] for temporary purposes. root[1] is the top.
+ */
+ b= (HUFF_ELEMENT*) queue.root[1];
+ /* Create a new element in a local (automatic) buffer. */
+ new_huff_el= element_buffer + i;
+ /*
+ The new element gets the sum of the two least incidence elements.
+ WARNING again: The reference of ->count works even if the queue
+ contains references into the huff_counts->counts array. This is
+ because HUFF_ELEMENT starts with the count and hence, the offset
+ of 'count' in HUFF_ELEMENT is zero.
+ */
+ new_huff_el->count= a->count + b->count;
+ /*
+ The Huffman algorithm assigns another bit to the code for a byte
+ every time that bytes incidence is combined (directly or indirectly)
+ to a new element as one of the two least incidence elements.
+ This means that one more bit per incidence of that byte is required
+ in the resulting file. So we add the new combined incidence as the
+ number of bits by which the result grows.
+ */
+ bits_packed+= (uint) (new_huff_el->count & 7);
+ bytes_packed+= new_huff_el->count/8;
+ /*
+ Replace the copied top element by the new element and re-order the
+ queue. This successively replaces the references to counts by
+ references to HUFF_ELEMENTs.
+ */
+ queue.root[1]= (byte*) new_huff_el;
queue_replaced(&queue);
}
DBUG_RETURN(bytes_packed+(bits_packed+7)/8);
@@ -1417,7 +1789,7 @@
}


- /* Fill in huff_tree decode tables */
+ /* Fill in huff_tree encode tables */

static int make_huff_decode_table(HUFF_TREE *huff_tree, uint trees)
{
@@ -1427,12 +1799,18 @@
if (huff_tree->tree_number > 0)
{
elements=huff_tree->counts->tree_buff ? huff_tree->elements : 256;
+ /*
+ We are prepared for codes with up to 32 bits in length (ulong)
+ and need a code length field (uchar). 'code' and 'code_len' are
+ arrays of ulong and uchar respectively.
+ */
if (!(huff_tree->code =
(ulong*) my_malloc(elements*
(sizeof(ulong)+sizeof(uchar)),
MYF(MY_WME | MY_ZEROFILL))))
return 1;
huff_tree->code_len=(uchar*) (huff_tree->code+elements);
+ /* Fill the codes and lenghts by traversing the tree. */
make_traverse_code_tree(huff_tree,huff_tree->root,32,0);
}
}
@@ -1440,23 +1818,77 @@
}


+/*
+ Traverse the Huffman tree and assign codes to the values.
+
+ SYNOPSIS
+ make_traverse_code_tree()
+ huff_tree The Huffman tree.
+ element The current element to start with.
+ size The number of remaining bits for the code.
+ code The current code value.
+
+ DESCRIPTION
+
+ When this is called with the root element, the size (number of
+ remaining bits) is set to 32. The code starts with 0x00000000. It
+ will be filled with bits from left to right. 'size' can also be seen
+ as the index of the bit to be set in the current stage. The root
+ element is most probably a node with two children. For a node, we
+ call the function recursively, after we adjust 'size' and 'code'.
+ For the root node this means that 'size' becomes 31 and the code for
+ the left child stays at 0x00000000 (bit 31 stays unset), while the
+ code for the right child becomes 0x80000000 (bit 31 is set). At the
+ next stage, bit 30 gets set or not. And so on. When a leaf is found,
+ it gets the high order (32 - size) bits assigned as its code.
+
+ RETURN
+ void
+*/
+
static void make_traverse_code_tree(HUFF_TREE *huff_tree,
HUFF_ELEMENT *element,
uint size, ulong code)
{
uint chr;
+ /*
+ 'a.leaf.null' takes the same place as 'a.nod.left'. If this is null,
+ then there is no left child and, hence no right child either. This
+ is a property of a binary tree. An element is either a node with two
+ childs, or a leaf without childs.
+ */
if (!element->a.leaf.null)
{
- chr=element->a.leaf.element_nr;
- huff_tree->code_len[chr]=(uchar) (32-size);
- huff_tree->code[chr]= (code >> size);
+ /* Get the byte code or the index of the column value. */
+ chr= element->a.leaf.element_nr;
+ /*
+ The code length at this stage is 32 bits less the remaining number
+ of bits.
+ */
+ huff_tree->code_len[chr]= (uchar) (32-size);
+ /*
+ The code for this value consists of that many highest order bits
+ of the current code value.
+ */
+ huff_tree->code[chr]= (code >> size);
+ /* Adjust the tree height if necessary. */
if (huff_tree->height < 32-size)
huff_tree->height= 32-size;
}
else
{
+ /* Non-leaf node. Decrement the remaining code size. */
size--;
+ DBUG_ASSERT(size != (uint) -1);
+ /*
+ Recursively traverse the tree to the left with the lowest bit of
+ the code unset.
+ */
make_traverse_code_tree(huff_tree,element->a.nod.left,size,code);
+ /*
+ Recursively traverse the tree to the right with the lowest bit of
+ the code set.
+ */
make_traverse_code_tree(huff_tree,element->a.nod.right,size,
code+((ulong) 1L << size));
}
@@ -1464,6 +1896,36 @@
}


+/*
+ Convert a value into binary digits.
+
+ SYNOPSIS
+ bindigits()
+ value The value.
+ length The number of low order bits to convert.
+
+ DESCRIPTION
+ The result string is in static storage. It is reused on every call.
+ So you cannot use it twice in one expression.
+
+ RETURN
+ A pointer to a static NUL-terminated string.
+ */
+
+static char *bindigits(ulong value, uint bits)
+{
+ static char digits[72];
+ char *ptr= digits;
+ uint idx= bits;
+
+ DBUG_ASSERT(bits < sizeof(digits));
+ while (idx)
+ *(ptr++)= '0' + ((value >> (--idx)) & 1);
+ *ptr= '\0';
+ return digits;
+}
+
+
/* Write header to new packed data file */

static int write_header(PACK_MRG_INFO *mrg,uint head_length,uint trees,
@@ -1495,10 +1957,15 @@
{
reg1 uint i;
uint huff_tree_bits;
+
huff_tree_bits=max_bit(trees ? trees-1 : 0);

+ PRINT2(("\n"));
+ DBG5(("=========================================== ===================\n"));
for (i=0 ; i++ < fields ; counts++)
{
+ DBG5(("---\n"));
+ /* We expect that en_fieldtype contains no more than 32 field types. */
write_bits((ulong) (int) counts->field_type,5);
write_bits(counts->pack_type,6);
if (counts->pack_type & PACK_TYPE_ZERO_FILL)
@@ -1506,6 +1973,10 @@
else
write_bits(counts->length_bits,5);
write_bits((ulong) counts->tree->tree_number-1,huff_tree_bits);
+ PRINT2(("column: %2u type: %2u pack: %2u zero: %4u lbits: %2u "
+ "tree: %2u length: %4u\n", i , counts->field_type,
+ counts->pack_type, counts->max_zero_fill, counts->length_bits,
+ counts->tree->tree_number, counts->field_length));
}
flush_bits();
return;
@@ -1518,30 +1989,52 @@
static my_off_t write_huff_tree(HUFF_TREE *huff_tree, uint trees)
{
uint i,int_length;
+ uint tree_no;
+ uint codes;
uint *packed_tree,*offset,length;
my_off_t elements;

+ /* Find the highest number of elements in the trees. */
for (i=length=0 ; i < trees ; i++)
if (huff_tree[i].tree_number > 0 && huff_tree[i].elements > length)
length=huff_tree[i].elements;
+ /*
+ Allocate a buffer for packing a decode tree. Two numbers per element
+ (left child and right child).
+ */
if (!(packed_tree=(uint*) my_alloca(sizeof(uint)*length*2)))
{
my_error(EE_OUTOFMEMORY,MYF(ME_BELL),sizeof(uint)* length*2);
return 0;
}

+ PRINT2(("\n"));
+ DBG5(("=========================================== ===================\n"));
+ tree_no= 0;
intervall_length=0;
for (elements=0; trees-- ; huff_tree++)
{
+ DBG5(("============================\n"));
+ /* Skip columns that have been joined with other columns. */
if (huff_tree->tree_number == 0)
continue; /* Deleted tree */
+ tree_no++;
+ /* Count the total number of elements (byte codes or column values). */
elements+=huff_tree->elements;
huff_tree->max_offset=2;
+ /* Build a tree of offsets and codes for decoding in 'packed_tree'. */
if (huff_tree->elements <= 1)
offset=packed_tree;
else
offset=make_offset_code_tree(huff_tree,huff_tree->root,packed_tree);
+
+ /* This should be the same as 'length' above. */
huff_tree->offset_bits=max_bit(huff_tree->max_offset);
+
+ /*
+ Since we collect only 8KB of distinct column values, and IS_OFFSET
+ is 32K, this should never happen.
+ */
if (huff_tree->max_offset >= IS_OFFSET)
{ /* This should be impossible */
VOID(fprintf(stderr,"Tree offset got too big: %d, aborted\n",
@@ -1557,6 +2050,7 @@
#endif
if (!huff_tree->counts->tree_buff)
{
+ /* We do a byte compression on this column. Mark with bit 0. */
write_bits(0,1);
write_bits(huff_tree->min_chr,8);
write_bits(huff_tree->elements,9);
@@ -1566,15 +2060,23 @@
}
else
{
- int_length=(uint) (huff_tree->counts->tree_pos -
- huff_tree->counts->tree_buff);
+ /* We have distinct column values for this column. Mark with bit 1. */
write_bits(1,1);
write_bits(huff_tree->elements,15);
+ int_length=(uint) (huff_tree->counts->tree_pos -
+ huff_tree->counts->tree_buff);
write_bits(int_length,16);
write_bits(huff_tree->char_bits,5);
write_bits(huff_tree->offset_bits,5);
intervall_length+=int_length;
}
+ PRINT2(("tree: %2u elements: %4u char_bits: %2u offset_bits: %2u "
+ "%s: %u\n", tree_no, huff_tree->elements, huff_tree->char_bits,
+ huff_tree->offset_bits, huff_tree->counts->tree_buff ?
+ "value_buffer_length" : "min_chr", huff_tree->counts->tree_buff ?
+ int_length : huff_tree->min_chr));
+
+ /* Check that the code tree length matches the element count. */
length=(uint) (offset-packed_tree);
if (length != huff_tree->elements*2-2)
printf("error: Huff-tree-length: %d != calc_length: %d\n",
@@ -1582,20 +2084,99 @@

for (i=0 ; i < length ; i++)
{
+ DBG5(("---\n"));
+ /*
+ Write the required offset/char bits
+ and add a bit for node/leaf.
+ */
if (packed_tree[i] & IS_OFFSET)
write_bits(packed_tree[i] - IS_OFFSET+ (1 << huff_tree->offset_bits),
huff_tree->offset_bits+1);
else
write_bits(packed_tree[i]-huff_tree->min_chr,huff_tree->char_bits+1);
+ PRINT4(("tree[0x%04x]: %s0x%04x \n", i, (packed_tree[i] & IS_OFFSET) ?
+ " -> " : "", (packed_tree[i] & IS_OFFSET) ?
+ packed_tree[i] - IS_OFFSET + i : packed_tree[i]));
}
flush_bits();
+
+ /*
+ Display coding tables and check their correctness.
+ */
+ codes= huff_tree->counts->tree_buff ? huff_tree->elements : 256;
+ for (i= 0; i < codes; i++)
+ {
+ ulong code;
+ uint bits;
+ uint len;
+ uint idx;
+
+ if (! (len= huff_tree->code_len[i]))
+ continue;
+ PRINT4(("code[0x%04x]: 0x%08lx bits: %2u bin: %s\n", i,
+ huff_tree->code[i], huff_tree->code_len[i],
+ bindigits(huff_tree->code[i], huff_tree->code_len[i])));
+
+ /* Check that the encode table decodes correctly. */
+ code= 0;
+ bits= 0;
+ idx= 0;
+ for (;
+ {
+ if (! len)
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "error: code not found with %u bits\n",
+ huff_tree->code_len[i]);
+ break;
+ }
+ code<<= 1;
+ code|= (huff_tree->code[i] >> (--len)) & 1;
+ bits++;
+ DBG5(("code: 0x%08lx bits: %2u bin: %s\n",
+ code, bits, bindigits(code, bits)));
+ if (bits > 8 * sizeof(code))
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "error: Huffman code too long: %u/%u\n",
+ bits, 8 * sizeof(code));
+ }
+ idx+= code & 1;
+ if (idx >= length)
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "error: illegal tree offset: %u/%u\n",
+ idx, length);
+ }
+ DBG5(("get real idx: 0x%04x\n", idx));
+ if (packed_tree[idx] & IS_OFFSET)
+ idx+= packed_tree[idx] & ~IS_OFFSET;
+ else
+ break; /* Hit a leaf. This contains the result value. */
+ DBG5(("new base idx: 0x%04x\n", idx));
+ }
+
+ if (packed_tree[idx] != i)
+ {
+ VOID(fflush(stdout));
+ fprintf(stderr, "error: decoded 0x%04x should be: 0x%04x\n",
+ packed_tree[idx], i);
+ }
+ } /*end for (codes)*/
+
+ /* Write column values in case of distinct column value compression. */
if (huff_tree->counts->tree_buff)
{
for (i=0 ; i < int_length ; i++)
+ {
write_bits((uint) (uchar) huff_tree->counts->tree_buff[i],8);
+ PRINT4(("column_values[0x%04x]: 0x%02x \n",
+ i, (uchar) huff_tree->counts->tree_buff[i]));
+ }
}
flush_bits();
}
+ PRINT2(("\n"));
my_afree((gptr) packed_tree);
return elements;
}
@@ -1607,23 +2188,43 @@
uint *prev_offset;

prev_offset= offset;
+ /*
+ 'a.leaf.null' takes the same place as 'a.nod.left'. If this is null,
+ then there is no left child and, hence no right child either. This
+ is a property of a binary tree. An element is either a node with two
+ childs, or a leaf without childs.
+
+ The current element is always a node with two childs. Go left first.
+ */
if (!element->a.nod.left->a.leaf.null)
{
+ /* Store the byte code or the index of the column value. */
offset[0] =(uint) element->a.nod.left->a.leaf.element_nr;
offset+=2;
}
else
{
+ /*
+ Recursively traverse the tree to the left. Mark it as an offset to
+ another tree node (in contrast to a byte code or column value index).
+ */
prev_offset[0]= IS_OFFSET+2;
offset=make_offset_code_tree(huff_tree,element->a.nod.left,offset+2);
}
+
+ /* Now, check the right child. */
if (!element->a.nod.right->a.leaf.null)
{
+ /* Store the byte code or the index of the column value. */
prev_offset[1]=element->a.nod.right->a.leaf.element_nr;
return offset;
}
else
{
+ /*
+ Recursively traverse the tree to the right. Mark it as an offset to
+ another tree node (in contrast to a byte code or column value index).
+ */
uint temp=(uint) (offset-prev_offset-1);
prev_offset[1]= IS_OFFSET+ temp;
if (huff_tree->max_offset < temp)
@@ -1650,6 +2251,7 @@
uint i,max_calc_length,pack_ref_length,min_record_lengt h,max_record_length,
intervall,field_length,max_pack_length,pack_blob_l ength;
my_off_t record_count;
+ char number[64];
ulong length,pack_length;
byte *record,*pos,*end_pos,*record_pos,*start_pos;
HUFF_COUNTS *count,*end_count;
@@ -1657,12 +2259,23 @@
MI_INFO *isam_file=mrg->file[0];
DBUG_ENTER("compress_isam_file");

+ /* Allocate a buffer for the records (excluding blobs). */
if (!(record=(byte*) my_alloca(isam_file->s->base.reclength)))
return -1;
+
end_count=huff_counts+isam_file->s->base.fields;
min_record_length= (uint) ~0;
max_record_length=0;

+ /*
+ Calculate the maximum number of bits required to pack the records.
+ Remember to understand 'max_zero_fill' as 'min_zero_fill'.
+ The tree height determines the maximum number of bits per value.
+ Some fields skip leading or trailing spaces or zeroes. The skipped
+ number of bytes is encoded by 'length_bits' bits.
+ Empty blobs and varchar are encoded with a single 1 bit. Other blobs
+ and varchar get a leading 0 bit.
+ */
for (i=max_calc_length=0 ; i < isam_file->s->base.fields ; i++)
{
if (!(huff_counts[i].pack_type & PACK_TYPE_ZERO_FILL))
@@ -1675,12 +2288,16 @@
max_calc_length+=huff_counts[i].tree->height;
else if (huff_counts[i].field_type == FIELD_BLOB ||
huff_counts[i].field_type == FIELD_VARCHAR)
- max_calc_length+=huff_counts[i].tree->height*huff_counts[i].max_length + huff_counts[i].length_bits +1;
+ max_calc_length+= (huff_counts[i].tree->height *
+ huff_counts[i].max_length +
+ huff_counts[i].length_bits + 1);
else
- max_calc_length+=
- (huff_counts[i].field_length - huff_counts[i].max_zero_fill)*
- huff_counts[i].tree->height+huff_counts[i].length_bits;
+ max_calc_length+= (huff_counts[i].tree->height *
+ (huff_counts[i].field_length -
+ huff_counts[i].max_zero_fill) +
+ huff_counts[i].length_bits);
}
+ /* Convert bits to bytes. Could we possibly lose up to 7 bits here? */
max_calc_length/=8;
if (max_calc_length < 254)
pack_ref_length=1;
@@ -1688,7 +2305,9 @@
pack_ref_length=3;
else
pack_ref_length=4;
+
record_count=0;
+ /* 'max_blob_length' is the max length of all blobs of a record. */
pack_blob_length=0;
if (isam_file->s->base.blobs)
{
@@ -1701,104 +2320,184 @@
}
max_pack_length=pack_ref_length+pack_blob_length;

+ DBG5(("=========================================== ===================\n"));
+ PRINT4(("===\n"));
mrg_reset(mrg);
while ((error=mrg_rrnd(mrg,record)) != HA_ERR_END_OF_FILE)
{
ulong tot_blob_length=0;
if (! error)
{
+ /* Request buffer space for the compressed data and the length info. */
if (flush_buffer(max_calc_length+max_pack_length))
break;
+ /* The current record starts here in the buffer. */
record_pos=file_buffer.pos;
+ /* Reserve space for the length info. */
file_buffer.pos+=max_pack_length;
+ /* Pack the columns. */
for (start_pos=record, count= huff_counts; count < end_count ; count++)
{
+ /* Locate the column in the record buffer. */
end_pos=start_pos+(field_length=count->field_length);
+ /* Select the decode tree. */
tree=count->tree;
+ PRINT4(("column: %2u type: %2u pack: %2u zero: %4u lbits: %2u "
+ "tree: %2u length: %4u\n", count - huff_counts + 1,
+ count->field_type, count->pack_type, count->max_zero_fill,
+ count->length_bits, count->tree->tree_number,
+ count->field_length));

+ /* Check if the column contains spaces only. */
if (count->pack_type & PACK_TYPE_SPACE_FIELDS)
{
for (pos=start_pos ; *pos == ' ' && pos < end_pos; pos++) ;
if (pos == end_pos)
{
+ /* Yes, spaces only. Write a bit and go to next column. */
+ PRINT4(("PACK_TYPE_SPACE_FIELDS spaces only, bits: 1\n---\n"));
write_bits(1,1);
start_pos=end_pos;
continue;
}
+ /* Not only spaces. Write a bit and continue with this column. */
+ PRINT4(("PACK_TYPE_SPACE_FIELDS not only spaces, bits: 1\n"));
write_bits(0,1);
}
+ /* Subtract trailing zeroes. */
end_pos-=count->max_zero_fill;
field_length-=count->max_zero_fill;

switch(count->field_type) {
case FIELD_SKIP_ZERO:
+ /* Check if the column contains zeroes only. */
if (!memcmp((byte*) start_pos,zero_string,field_length))
{
+ /* Yes, zeroes only. Write a bit and go to next column. */
+ PRINT4(("FIELD_SKIP_ZERO zeroes only, bits: 1\n"));
write_bits(1,1);
start_pos=end_pos;
break;
}
+ /* Not only zeroes. Write a bit and continue with this column. */
+ PRINT4(("FIELD_SKIP_ZERO not only zeroes, bits: 1\n"));
write_bits(0,1);
/* Fall through */
case FIELD_NORMAL:
+ /* Encode all significant bytes. */
+ PRINT4(("FIELD_NORMAL %u bytes\n", end_pos - start_pos));
for ( ; start_pos < end_pos ; start_pos++)
+ {
+ PRINT4(("value: 0x%02x code: 0x%08lx bits: %2u bin: %s\n",
+ (uchar) *start_pos, tree->code[(uchar) *start_pos],
+ (uint) tree->code_len[(uchar) *start_pos],
+ bindigits(tree->code[(uchar) *start_pos],
+ (uint) tree->code_len[(uchar) *start_pos])));
write_bits(tree->code[(uchar) *start_pos],
(uint) tree->code_len[(uchar) *start_pos]);
+ }
break;
case FIELD_SKIP_ENDSPACE:
+ /* Count trailing spaces. */
for (pos=end_pos ; pos > start_pos && pos[-1] == ' ' ; pos--) ;
- length=(uint) (end_pos-pos);
+ length= (ulong) (end_pos - pos);
+ /* If not all trailing spaces are to be marked, add a bit. */
if (count->pack_type & PACK_TYPE_SELECTED)
{
if (length > count->min_space)
{
+ PRINT4(("FIELD_SKIP_ENDSPACE more than min_space, bits: 1\n"
+ "FIELD_SKIP_ENDSPACE skip %lu/%u bytes, bits: %2u\n",
+ length, field_length, count->length_bits));
write_bits(1,1);
write_bits(length,count->length_bits);
}
else
{
+ PRINT4(("FIELD_SKIP_ENDSPACE not more than min_space, "
+ "bits: 1\n"));
write_bits(0,1);
pos=end_pos;
}
}
else
- write_bits(length,count->length_bits);
+ {
+ PRINT4(("FIELD_SKIP_ENDSPACE skip %lu/%u bytes, bits: %2u\n",
+ length, field_length, count->length_bits));
+ write_bits(length,count->length_bits);
+ }
+ /* Encode all significant bytes. */
+ PRINT4(("FIELD_SKIP_ENDSPACE %u bytes\n", pos - start_pos));
for ( ; start_pos < pos ; start_pos++)
+ {
+ PRINT4(("value: 0x%02x code: 0x%08lx bits: %2u bin: %s\n",
+ (uchar) *start_pos, tree->code[(uchar) *start_pos],
+ (uint) tree->code_len[(uchar) *start_pos],
+ bindigits(tree->code[(uchar) *start_pos],
+ (uint) tree->code_len[(uchar) *start_pos])));
write_bits(tree->code[(uchar) *start_pos],
(uint) tree->code_len[(uchar) *start_pos]);
+ }
start_pos=end_pos;
break;
case FIELD_SKIP_PRESPACE:
+ /* Count leading spaces. */
for (pos=start_pos ; pos < end_pos && pos[0] == ' ' ; pos++) ;
- length=(uint) (pos-start_pos);
+ length= (ulong) (pos - start_pos);
+ /* If not all leading spaces are to be marked, add a bit. */
if (count->pack_type & PACK_TYPE_SELECTED)
{
if (length > count->min_space)
{
+ PRINT4(("FIELD_SKIP_PRESPACE more than min_space, bits: 1\n"
+ "FIELD_SKIP_PRESPACE skip %lu/%u bytes, bits: %2u\n",
+ length, field_length, count->length_bits));
write_bits(1,1);
write_bits(length,count->length_bits);
}
else
{
+ PRINT4(("FIELD_SKIP_PRESPACE not more than min_space, "
+ "bits: 1\n"));
pos=start_pos;
write_bits(0,1);
}
}
else
+ {
+ PRINT4(("FIELD_SKIP_PRESPACE skip %lu/%u bytes, bits: %2u\n",
+ length, field_length, count->length_bits));
write_bits(length,count->length_bits);
+ }
+ /* Encode all significant bytes. */
+ PRINT4(("FIELD_SKIP_PRESPACE %u bytes\n", end_pos - start_pos));
for (start_pos=pos ; start_pos < end_pos ; start_pos++)
+ {
+ PRINT4(("value: 0x%02x code: 0x%08lx bits: %2u bin: %s\n",
+ (uchar) *start_pos, tree->code[(uchar) *start_pos],
+ (uint) tree->code_len[(uchar) *start_pos],
+ bindigits(tree->code[(uchar) *start_pos],
+ (uint) tree->code_len[(uchar) *start_pos])));
write_bits(tree->code[(uchar) *start_pos],
(uint) tree->code_len[(uchar) *start_pos]);
+ }
break;
case FIELD_CONSTANT:
case FIELD_ZERO:
case FIELD_CHECK:
+ /* Do not write anything for these. */
+ PRINT4(("FIELD_CONSTANT/ZERO/CHECK\n"));
start_pos=end_pos;
break;
case FIELD_INTERVALL:
+ /* Search the column value in the tree. */
global_count=count;
pos=(byte*) tree_search(&count->int_tree,start_pos);
+ /* Encode the value. */
intervall=(uint) (pos - count->tree_buff)/field_length;
+ PRINT4(("FIELD_INTERVALL\nindex: %4u code: 0x%08lx bits: %2u\n",
+ intervall, tree->code[intervall],
+ (uint) tree->code_len[intervall]));
write_bits(tree->code[intervall],(uint) tree->code_len[intervall]);
start_pos=end_pos;
break;
@@ -1807,21 +2506,35 @@
ulong blob_length=_mi_calc_blob_length(field_length-
mi_portable_sizeof_char_ptr,
start_pos);
+ /* Empty blobs are encoded with a single 1 bit. */
if (!blob_length)
{
- write_bits(1,1); /* Empty blob */
+ PRINT4(("FIELD_BLOB empty, bits: 1\n"));
+ write_bits(1,1);
}
else
{
byte *blob,*blob_end;
+ PRINT4(("FIELD_BLOB not empty, bits: 1\n"));
write_bits(0,1);
+ /* Write the blob length. */
+ PRINT4(("FIELD_BLOB %lu bytes, bits: %2u\n",
+ blob_length, count->length_bits));
write_bits(blob_length,count->length_bits);
memcpy_fixed(&blob,end_pos-mi_portable_sizeof_char_ptr,
sizeof(char*));
blob_end=blob+blob_length;
+ /* Encode the blob bytes. */
for ( ; blob < blob_end ; blob++)
+ {
+ PRINT4(("value: 0x%02x code: 0x%08lx bits: %2u bin: %s\n",
+ (uchar) *blob, tree->code[(uchar) *blob],
+ (uint) tree->code_len[(uchar) *blob],
+ bindigits(tree->code[(uchar) *start_pos],
+ (uint) tree->code_len[(uchar) *start_pos])));
write_bits(tree->code[(uchar) *blob],
(uint) tree->code_len[(uchar) *blob]);
+ }
tot_blob_length+=blob_length;
}
start_pos= end_pos;
@@ -1830,18 +2543,32 @@
case FIELD_VARCHAR:
{
ulong col_length= uint2korr(start_pos);
+ /* Empty varchar are encoded with a single 1 bit. */
if (!col_length)
{
+ PRINT4(("FIELD_VARCHAR empty, bits: 1\n"));
write_bits(1,1); /* Empty varchar */
}
else
{
byte *end=start_pos+2+col_length;
+ PRINT4(("FIELD_VARCHAR not empty, bits: 1\n"));
write_bits(0,1);
+ /* Write the varchar length. */
+ PRINT4(("FIELD_VARCHAR %lu bytes, bits: %2u\n",
+ col_length, count->length_bits));
write_bits(col_length,count->length_bits);
+ /* Encode the varchar bytes. */
for (start_pos+=2 ; start_pos < end ; start_pos++)
+ {
+ PRINT4(("value: 0x%02x code: 0x%08lx bits: %2u bin: %s\n",
+ (uchar) *start_pos, tree->code[(uchar) *start_pos],
+ (uint) tree->code_len[(uchar) *start_pos],
+ bindigits(tree->code[(uchar) *start_pos],
+ (uint) tree->code_len[(uchar) *start_pos])));
write_bits(tree->code[(uchar) *start_pos],
(uint) tree->code_len[(uchar) *start_pos]);
+ }
}
start_pos= end_pos;
break;
@@ -1849,15 +2576,27 @@
case FIELD_LAST:
abort(); /* Impossible */
}
+ /* Skip zero bytes if there are any. */
start_pos+=count->max_zero_fill;
+ PRINT4(("---\n"));
}
flush_bits();
+ /* Calculate the length of the compressed record. */
length=(ulong) (file_buffer.pos-record_pos)-max_pack_length;
+ /*
+ Insert the compressed record length and the sum of the blob
+ lengths at the beginning of the record buffer.
+ */
pack_length=save_pack_length(record_pos,length);
if (pack_blob_length)
pack_length+=save_pack_length(record_pos+pack_leng th,tot_blob_length);
-
- /* Correct file buffer if the header was smaller */
+ PRINT3(("record: %lu length: %lu blob-length: %lu length-bytes: %lu\n",
+ (ulong) record_count, length, tot_blob_length, pack_length));
+ PRINT4(("===\n"));
+ /*
+ If the packed lengths are smaller than the reserved space, move
+ the compressed data behind the length bytes.
+ */
if (pack_length != max_pack_length)
{
bmove(record_pos+pack_length,record_pos+max_pack_l ength,length);
@@ -1867,7 +2606,8 @@
min_record_length=(uint) length;
if (length > (ulong) max_record_length)
max_record_length=(uint) length;
- if (write_loop && ++record_count % WRITE_COUNT == 0)
+ record_count++;
+ if (write_loop && (verbose <= 2) && (record_count % WRITE_COUNT == 0))
{
printf("%lu\r",(ulong) record_count); VOID(fflush(stdout));
}
@@ -1881,6 +2621,8 @@
{
fprintf(stderr,"%s: Got error %d reading records\n",my_progname,error);
}
+ VOID(longlong2str((longlong) record_count, number, 10));
+ PRINT2(("wrote %s records.\n", number));

my_afree((gptr) record);
mrg->ref_length=max_pack_length;
@@ -1963,45 +2705,105 @@
my_free((gptr) file_buffer.buffer,MYF(0));
}

- /* output `bits` low bits of `value' */

-static void write_bits (register ulong value, register uint bits)
-{
- if ((file_buffer.bits-=(int) bits) >= 0)
+/*
+ Write low order bits of a value to the file buffer.
+
+ SYNOPSIS
+ write_bits()
+ value The value to write.
+ bits The number of low order bits to write.
+
+ WARNING
+ All bits of value above 'bits' must be zero.
+
+ RETURN
+ void
+*/
+
+static void write_bits(register ulong value, register uint bits)
+{
+ DBUG_ASSERT(((bits < 8 * sizeof(value)) && ! (value >> bits)) ||
+ (bits == 8 * sizeof(value)));
+ DBG5(("enter buffer: 0x%08x bits: %2u bin: %s\n",
+ file_buffer.byte, BITS_SAVED - file_buffer.bits,
+ bindigits(file_buffer.byte >> file_buffer.bits,
+ BITS_SAVED - file_buffer.bits)));
+ DBG5(("enter value: 0x%08lx bits: %2u bin: %s\n",
+ value, bits, bindigits(value, bits)));
+
+ /* Try to put the bits into the current buffer word first. */
+ if ((file_buffer.bits-= (int) bits) >= 0)
{
- file_buffer.byte|=value << file_buffer.bits;
+ /* They fit. */
+ file_buffer.byte|= value << file_buffer.bits;
}
else
{
+ /* Not enough space in the current buffer word. */
reg3 uint byte_buff;
+
+ /*
+ Calculate the number of bits which have to go into the next word.
+ file_buffer.bits became negative in the 'if' expression above.
+ */
bits= (uint) -file_buffer.bits;
+ /*
+ Copy the buffer word plus the value - reduced by that number of bits -
+ to the temp word.
+ */
byte_buff=file_buffer.byte | (uint) (value >> bits);
+ /* Copy the temp word - byte by byte, high first - to the file buffer. */
#if BITS_SAVED == 32
+ DBG5(("bit buffer I/O: 0x%02x bits: 8 bin: %s\n",
+ (uchar) (byte_buff >> 24), bindigits(byte_buff >> 24, 8)));
+ DBG5(("bit buffer I/O: 0x%02x bits: 8 bin: %s\n",
+ (uchar) (byte_buff >> 16), bindigits(byte_buff >> 16, 8)));
*file_buffer.pos++= (byte) (byte_buff >> 24) ;
*file_buffer.pos++= (byte) (byte_buff >> 16) ;
#endif
+ DBG5(("bit buffer I/O: 0x%02x bits: 8 bin: %s\n",
+ (uchar) (byte_buff >> 8), bindigits(byte_buff >> 8, 8)));
+ DBG5(("bit buffer I/O: 0x%02x bits: 8 bin: %s\n",
+ (uchar) (byte_buff), bindigits(byte_buff, 8)));
*file_buffer.pos++= (byte) (byte_buff >> 8) ;
*file_buffer.pos++= (byte) byte_buff;

+ /* Clear the copied bits from the value. */
value&=(1 << bits)-1;
+ DBG5(("prelim value: 0x%08lx bits: %2u bin: %s\n",
+ value, bits, bindigits(value, bits)));
+
+ /*
+ In the case of a 16-bit machine, we may have more bits left than
+ fit into the buffer word. Put them byte by byte to the file buffer
+ until the remaining bits will fit.
+ */
#if BITS_SAVED == 16
if (bits >= sizeof(uint))
{
bits-=8;
+ DBG5(("bit buffer I/O: 0x%02x bits: 8 bin: %s\n",
+ (uchar) (value >> bits), bindigits(value >> bits, 8)));
*file_buffer.pos++= (uchar) (value >> bits);
value&= (1 << bits)-1;
if (bits >= sizeof(uint))
{
bits-=8;
+ DBG5(("bit buffer I/O: 0x%02x bits: 8 bin: %s\n",
+ (uchar) (value >> bits), bindigits(value >> bits, 8)));
*file_buffer.pos++= (uchar) (value >> bits);
value&= (1 << bits)-1;
}
}
#endif
+ /* If the file buffer became full, flush it. */
if (file_buffer.pos >= file_buffer.end)
VOID(flush_buffer((uint) ~0));
- file_buffer.bits=(int) (BITS_SAVED - bits);
- file_buffer.byte=(uint) (value << (BITS_SAVED - bits));
+ /* Save the number of bits left for the buffer word. */
+ file_buffer.bits= (int) (BITS_SAVED - bits);
+ /* Save the remaining bits in the buffer word. */
+ file_buffer.byte= (uint) (value << (BITS_SAVED - bits));
}
return;
}
@@ -2018,6 +2820,8 @@
while (bits > 0)
{
bits-=8;
+ DBG5(("bit buffer I/O: 0x%02x bits: 8 bin: %s\n",
+ (uchar) (byte_buff >> bits), bindigits(byte_buff >> bits, 8)));
*file_buffer.pos++= (byte) (uchar) (byte_buff >> bits) ;
}
file_buffer.bits=BITS_SAVED;

--
MySQL Internals Mailing List
For list archives: http://lists.mysql.com/internals
To unsubscribe: http://lists.mysql.com/internals?uns...ie.nctu.edu.tw