| List: | Internals | « Previous MessageNext Message » | |
| From: | ingo | Date: | March 21 2005 8:02pm |
| Subject: | bk commit into 5.1 tree (ingo:1.1794) BUG#8321 | ||
| View as plain text | |||
Below is the list of changes that have just been committed into a local 5.1 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/installing-source-tree.html ChangeSet 1.1794 05/03/21 20:02:45 ingo@stripped +3 -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, and some additional checks. myisam/myisampack.c 1.40 05/03/21 19:57:28 ingo@stripped +875 -35 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/mi_packrec.c 1.30 05/03/21 19:57:28 ingo@stripped +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.69 05/03/21 19:57:28 ingo@stripped +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-5.1-bug8321 --- 1.68/include/my_base.h Fri Feb 18 13:14:26 2005 +++ 1.69/include/my_base.h Mon Mar 21 19:57:28 2005 @@ -365,6 +365,7 @@ #define HA_STATE_EXTEND_BLOCK 2048 #define HA_STATE_RNEXT_SAME 4096 /* rnext_same was called */ +/* myisampack expects no more than 32 field types. */ enum en_fieldtype { FIELD_LAST=-1,FIELD_NORMAL,FIELD_SKIP_ENDSPACE,FIELD_SKIP_PRESPACE, FIELD_SKIP_ZERO,FIELD_BLOB,FIELD_CONSTANT,FIELD_INTERVALL,FIELD_ZERO, --- 1.29/myisam/mi_packrec.c Thu Feb 24 05:36:23 2005 +++ 1.30/myisam/mi_packrec.c Mon Mar 21 19:57:28 2005 @@ -417,7 +417,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.39/myisam/myisampack.c Sat Dec 18 04:19:15 2004 +++ 1.40/myisam/myisampack.c Mon Mar 21 19:57:28 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_) do {if (verbose >= 2) printf _arglist_;} while (0) +#define PRINT3(_arglist_) do {if (verbose >= 3) printf _arglist_;} while (0) +#define PRINT4(_arglist_) do {if (verbose >= 4) printf _arglist_;} while (0) +#ifdef EXTRA_DEBUG +#define DBG5(_arglist_) do {if (verbose >= 5) printf _arglist_;} while (0) +#else +#define DBG5(_arglist_) do {} while (0) +#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 current_byte; + int bits; /* The number of bits free in 'byte'. */ + uint current_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_fields,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 { @@ -259,7 +274,7 @@ 0, 0, 0, GET_STR, REQUIRED_ARG, 0, 0, 0, 0, 0, 0}, {"test", 't', "Don't pack table, only test packing it.", 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0}, - {"verbose", 'v', "Write info about progress and packing result.", + {"verbose", 'v', "Write info about progress and packing result. Use many -v for more verbosity!", 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0}, {"version", 'V', "Output version information and exit.", 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0}, @@ -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 + temporary 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_SEEK_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,tot_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,huff_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) @@ -733,6 +811,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"); @@ -761,10 +842,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++, @@ -772,7 +856,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; @@ -790,10 +893,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; } } @@ -803,15 +913,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) @@ -819,18 +935,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) @@ -838,6 +961,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; @@ -856,27 +981,46 @@ end_pos= 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++; @@ -890,11 +1034,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); @@ -943,9 +1117,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; @@ -953,14 +1132,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)+records/8; + /* 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; @@ -968,9 +1155,16 @@ huff_counts->bytes_packed=old_length- records/8; goto found_pack; } + /* 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 && @@ -1002,6 +1196,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; @@ -1011,6 +1210,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_counts->max_pre_space, @@ -1169,8 +1373,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) { @@ -1181,12 +1401,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]) @@ -1200,6 +1422,7 @@ found=2; } + /* When using 'tree_buff' we can have more that 256 values. */ if (queue.max_elements < found) { delete_queue(&queue); @@ -1207,6 +1430,7 @@ return -1; } + /* Allocate or reallocate an element buffer for the Huffman tree. */ if (!huff_tree->element_buffer) { if (!(huff_tree->element_buffer= @@ -1234,15 +1458,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 { @@ -1251,7 +1485,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]) @@ -1263,8 +1505,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; @@ -1275,21 +1522,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++) { + /* + 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; - new_huff_el->a.nod.left=a; /* lesser in left */ + /* 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); } @@ -1308,7 +1587,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) @@ -1325,8 +1623,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) @@ -1336,6 +1649,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++) { @@ -1344,31 +1671,76 @@ 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; + /* + 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); } @@ -1422,7 +1794,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) { @@ -1432,12 +1804,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); } } @@ -1445,23 +1823,76 @@ } +/* + 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) { + /* 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--; + /* + 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)); } @@ -1469,6 +1900,68 @@ } +/* + Convert a value into binary digits. + + SYNOPSIS + bindigits() + value The value. + length The number of low order bits to convert. + + NOTE + 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(idx < sizeof(digits)); + while (idx) + *(ptr++)= '0' + ((value >> (--idx)) & 1); + *ptr= '\0'; + return digits; +} + + +/* + Convert a value into hexadecimal digits. + + SYNOPSIS + hexdigits() + value The value. + + NOTE + 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 *hexdigits(ulong value) +{ + static char digits[20]; + char *ptr= digits; + uint idx= 2 * sizeof(value); /* Two hex digits per byte. */ + + DBUG_ASSERT(idx < sizeof(digits)); + while (idx) + { + if ((*(ptr++)= '0' + ((value >> (4 * (--idx))) & 0xf)) > '9') + *(ptr - 1)+= 'a' - '9' - 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, @@ -1500,10 +1993,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) @@ -1511,6 +2009,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; @@ -1523,30 +2025,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++) { + /* Skip columns that have been joined with other columns. */ if (huff_tree->tree_number == 0) continue; /* Deleted tree */ + tree_no++; + DBG5(("============================\n")); + /* 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", @@ -1562,6 +2086,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); @@ -1573,6 +2098,7 @@ { 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); write_bits(int_length,16); @@ -1580,6 +2106,13 @@ 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", @@ -1587,20 +2120,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%s bits: %2u bin: %s\n", i, + hexdigits(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%s bits: %2u bin: %s\n", + hexdigits(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; } @@ -1612,23 +2224,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) @@ -1655,6 +2287,7 @@ uint i,max_calc_length,pack_ref_length,min_record_length,max_record_length, intervall,field_length,max_pack_length,pack_blob_length; 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; @@ -1662,12 +2295,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)) @@ -1680,12 +2324,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. Can we lose up to 7 bits here? */ max_calc_length/=8; if (max_calc_length < 254) pack_ref_length=1; @@ -1693,7 +2341,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) { @@ -1706,105 +2356,189 @@ } 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 code 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%s bits: %2u bin: %s\n", + (uchar) *start_pos, + hexdigits(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); + /* 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 + { + 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%s bits: %2u bin: %s\n", + (uchar) *start_pos, + hexdigits(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); + /* 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%s bits: %2u bin: %s\n", + (uchar) *start_pos, + hexdigits(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, count->int_tree.custom_arg); + /* Encode the value. */ intervall=(uint) (pos - count->tree_buff)/field_length; + PRINT4(("FIELD_INTERVALL\n" + "index: %4u code: 0x%s bits: %2u\n", + intervall, hexdigits(tree->code[intervall]), + (uint) tree->code_len[intervall])); write_bits(tree->code[intervall],(uint) tree->code_len[intervall]); start_pos=end_pos; break; @@ -1813,21 +2547,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%s bits: %2u bin: %s\n", + (uchar) *blob, hexdigits(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; @@ -1838,18 +2586,33 @@ uint pack_length= HA_VARCHAR_PACKLENGTH(count->field_length-1); ulong col_length= (pack_length == 1 ? (uint) *(uchar*) start_pos : 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+pack_length+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+=pack_length ; start_pos < end ; start_pos++) + { + PRINT4(("value: 0x%02x code: 0x%s bits: %2u bin: %s\n", + (uchar) *start_pos, + hexdigits(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; @@ -1857,15 +2620,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_length,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_length,length); @@ -1875,7 +2650,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)); } @@ -1889,6 +2665,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; @@ -1971,44 +2749,104 @@ my_free((gptr) file_buffer.buffer,MYF(0)); } - /* output `bits` low bits of `value' */ -static void write_bits (register ulong value, register uint bits) -{ +/* + 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%s bits: %2u bin: %s\n", + hexdigits(file_buffer.current_byte), BITS_SAVED - file_buffer.bits, + bindigits(file_buffer.current_byte >> file_buffer.bits, + BITS_SAVED - file_buffer.bits))); + DBG5(("enter value: 0x%s bits: %2u bin: %s\n", + hexdigits(value), bits, bindigits(value, bits))); + + /* Try to put the bits into the current buffer word first. */ if ((file_buffer.bits-=(int) bits) >= 0) { + /* They fit. */ file_buffer.current_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.current_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%s bits: %2u bin: %s\n", + hexdigits(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)); + /* 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.current_byte=(uint) (value << (BITS_SAVED - bits)); } return; @@ -2026,6 +2864,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;
| Thread | ||
|---|---|---|
| • bk commit into 5.1 tree (ingo:1.1794) BUG#8321 | ingo | 21 Mar |
© 1995-2008 MySQL AB, 2008-2009 Sun Microsystems, Inc.
Page generated in 0.934 sec. using MySQL 5.1.14-beta-log