1 /* Copyright (c) 2000, 2021, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22
23 /* Pack MyISAM file */
24
25 #ifndef USE_MY_FUNC
26 #define USE_MY_FUNC /* We need at least my_malloc */
27 #endif
28
29 #include "myisamdef.h"
30 #include "my_default.h"
31 #include <queues.h>
32 #include <my_tree.h>
33 #include "mysys_err.h"
34 #ifndef __GNU_LIBRARY__
35 #define __GNU_LIBRARY__ /* Skip warnings in getopt.h */
36 #endif
37 #include <my_getopt.h>
38 #include <assert.h>
39 #include <welcome_copyright_notice.h> // ORACLE_WELCOME_COPYRIGHT_NOTICE
40
41 #if SIZEOF_LONG_LONG > 4
42 #define BITS_SAVED 64
43 #else
44 #define BITS_SAVED 32
45 #endif
46
47 #define IS_OFFSET ((uint) 32768) /* Bit if offset or char in tree */
48 #define HEAD_LENGTH 32
49 #define ALLOWED_JOIN_DIFF 256 /* Diff allowed to join trees */
50
51 #define DATA_TMP_EXT ".TMD"
52 #define OLD_EXT ".OLD"
53 #define FRM_EXT ".frm"
54 #define WRITE_COUNT MY_HOW_OFTEN_TO_WRITE
55
56 struct st_file_buffer {
57 File file;
58 uchar *buffer,*pos,*end;
59 my_off_t pos_in_file;
60 int bits;
61 ulonglong bitbucket;
62 };
63
64 struct st_huff_tree;
65 struct st_huff_element;
66
67 typedef struct st_huff_counts {
68 uint field_length,max_zero_fill;
69 uint pack_type;
70 uint max_end_space,max_pre_space,length_bits,min_space;
71 ulong max_length;
72 enum en_fieldtype field_type;
73 struct st_huff_tree *tree; /* Tree for field */
74 my_off_t counts[256];
75 my_off_t end_space[8];
76 my_off_t pre_space[8];
77 my_off_t tot_end_space,tot_pre_space,zero_fields,empty_fields,bytes_packed;
78 TREE int_tree; /* Tree for detecting distinct column values. */
79 uchar *tree_buff; /* Column values, 'field_length' each. */
80 uchar *tree_pos; /* Points to end of column values in 'tree_buff'. */
81 } HUFF_COUNTS;
82
83 typedef struct st_huff_element HUFF_ELEMENT;
84
85 /*
86 WARNING: It is crucial for the optimizations in calc_packed_length()
87 that 'count' is the first element of 'HUFF_ELEMENT'.
88 */
89 struct st_huff_element {
90 my_off_t count;
91 union un_element {
92 struct st_nod {
93 HUFF_ELEMENT *left,*right;
94 } nod;
95 struct st_leaf {
96 HUFF_ELEMENT *null;
97 uint element_nr; /* Number of element */
98 } leaf;
99 } a;
100 };
101
102
103 typedef struct st_huff_tree {
104 HUFF_ELEMENT *root,*element_buffer;
105 HUFF_COUNTS *counts;
106 uint tree_number;
107 uint elements;
108 my_off_t bytes_packed;
109 uint tree_pack_length;
110 uint min_chr,max_chr,char_bits,offset_bits,max_offset,height;
111 ulonglong *code;
112 uchar *code_len;
113 } HUFF_TREE;
114
115
116 typedef struct st_isam_mrg {
117 MI_INFO **file,**current,**end;
118 uint free_file;
119 uint count;
120 uint min_pack_length; /* Theese is used by packed data */
121 uint max_pack_length;
122 uint ref_length;
123 uint max_blob_length;
124 my_off_t records;
125 /* true if at least one source file has at least one disabled index */
126 my_bool src_file_has_indexes_disabled;
127 } PACK_MRG_INFO;
128
129
130 extern int main(int argc,char * *argv);
131 static void get_options(int *argc,char ***argv);
132 static MI_INFO *open_isam_file(char *name,int mode);
133 static my_bool open_isam_files(PACK_MRG_INFO *mrg,char **names,uint count);
134 static int compress(PACK_MRG_INFO *file,char *join_name);
135 static int create_dest_frm(char *source_table, char *dest_table);
136 static HUFF_COUNTS *init_huff_count(MI_INFO *info,my_off_t records);
137 static void free_counts_and_tree_and_queue(HUFF_TREE *huff_trees,
138 uint trees,
139 HUFF_COUNTS *huff_counts,
140 uint fields);
141 static int compare_tree(void* cmp_arg MY_ATTRIBUTE((unused)),
142 const uchar *s,const uchar *t);
143 static int get_statistic(PACK_MRG_INFO *mrg,HUFF_COUNTS *huff_counts);
144 static void check_counts(HUFF_COUNTS *huff_counts,uint trees,
145 my_off_t records);
146 static int test_space_compress(HUFF_COUNTS *huff_counts,my_off_t records,
147 uint max_space_length,my_off_t *space_counts,
148 my_off_t tot_space_count,
149 enum en_fieldtype field_type);
150 static HUFF_TREE* make_huff_trees(HUFF_COUNTS *huff_counts,uint trees);
151 static int make_huff_tree(HUFF_TREE *tree,HUFF_COUNTS *huff_counts);
152 static int compare_huff_elements(void *not_used, uchar *a,uchar *b);
153 static int save_counts_in_queue(uchar *key,element_count count,
154 HUFF_TREE *tree);
155 static my_off_t calc_packed_length(HUFF_COUNTS *huff_counts,uint flag);
156 static uint join_same_trees(HUFF_COUNTS *huff_counts,uint trees);
157 static int make_huff_decode_table(HUFF_TREE *huff_tree,uint trees);
158 static void make_traverse_code_tree(HUFF_TREE *huff_tree,
159 HUFF_ELEMENT *element,uint size,
160 ulonglong code);
161 static int write_header(PACK_MRG_INFO *isam_file, uint header_length,uint trees,
162 my_off_t tot_elements,my_off_t filelength);
163 static void write_field_info(HUFF_COUNTS *counts, uint fields,uint trees);
164 static my_off_t write_huff_tree(HUFF_TREE *huff_tree,uint trees);
165 static uint *make_offset_code_tree(HUFF_TREE *huff_tree,
166 HUFF_ELEMENT *element,
167 uint *offset);
168 static uint max_bit(uint value);
169 static int compress_isam_file(PACK_MRG_INFO *file,HUFF_COUNTS *huff_counts);
170 static char *make_new_name(char *new_name,char *old_name);
171 static char *make_old_name(char *new_name,char *old_name);
172 static void init_file_buffer(File file,pbool read_buffer);
173 static int flush_buffer(ulong neaded_length);
174 static void end_file_buffer(void);
175 static void write_bits(ulonglong value, uint bits);
176 static void flush_bits(void);
177 static int save_state(MI_INFO *isam_file,PACK_MRG_INFO *mrg,my_off_t new_length,
178 ha_checksum crc);
179 static int save_state_mrg(File file,PACK_MRG_INFO *isam_file,my_off_t new_length,
180 ha_checksum crc);
181 static int mrg_close(PACK_MRG_INFO *mrg);
182 static int mrg_rrnd(PACK_MRG_INFO *info,uchar *buf);
183 static void mrg_reset(PACK_MRG_INFO *mrg);
184 #if !defined(NDEBUG)
185 static void fakebigcodes(HUFF_COUNTS *huff_counts, HUFF_COUNTS *end_count);
186 static int fakecmp(my_off_t **count1, my_off_t **count2);
187 #endif
188
189
190 static int error_on_write=0,test_only=0,verbose=0,silent=0,
191 write_loop=0,force_pack=0, isamchk_neaded=0;
192 static int tmpfile_createflag=O_RDWR | O_TRUNC | O_EXCL;
193 static my_bool backup, opt_wait;
194 /*
195 tree_buff_length is somewhat arbitrary. The bigger it is the better
196 the chance to win in terms of compression factor. On the other hand,
197 this table becomes part of the compressed file header. And its length
198 is coded with 16 bits in the header. Hence the limit is 2**16 - 1.
199 */
200 static uint tree_buff_length= 65536 - MALLOC_OVERHEAD;
201 static char tmp_dir[FN_REFLEN]={0},*join_table;
202 static my_off_t intervall_length;
203 static ha_checksum glob_crc;
204 static struct st_file_buffer file_buffer;
205 static QUEUE queue;
206 static HUFF_COUNTS *global_count;
207 static char zero_string[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
208 static const char *load_default_groups[]= { "myisampack",0 };
209
keycache_thread_var()210 extern st_keycache_thread_var *keycache_thread_var()
211 {
212 return &main_thread_keycache_var;
213 }
214
215 /* The main program */
216
main(int argc,char ** argv)217 int main(int argc, char **argv)
218 {
219 int error,ok;
220 PACK_MRG_INFO merge;
221 char **default_argv;
222 MY_INIT(argv[0]);
223
224 memset(&main_thread_keycache_var, 0, sizeof(st_keycache_thread_var));
225 mysql_cond_init(PSI_NOT_INSTRUMENTED,
226 &main_thread_keycache_var.suspend);
227
228 if (load_defaults("my",load_default_groups,&argc,&argv))
229 exit(1);
230
231 default_argv= argv;
232 get_options(&argc,&argv);
233
234 error=ok=isamchk_neaded=0;
235 if (join_table)
236 {
237 /*
238 Join files into one and create FRM file for the compressed table only if
239 the compression succeeds
240 */
241 if (open_isam_files(&merge,argv,(uint) argc) ||
242 compress(&merge, join_table) || create_dest_frm(argv[0], join_table))
243 error=1;
244 }
245 else while (argc--)
246 {
247 MI_INFO *isam_file;
248 if (!(isam_file=open_isam_file(*argv++,O_RDWR)))
249 error=1;
250 else
251 {
252 merge.file= &isam_file;
253 merge.current=0;
254 merge.free_file=0;
255 merge.count=1;
256 if (compress(&merge,0))
257 error=1;
258 else
259 ok=1;
260 }
261 }
262 if (ok && isamchk_neaded && !silent)
263 puts("Remember to run myisamchk -rq on compressed tables");
264 (void) fflush(stdout);
265 (void) fflush(stderr);
266 free_defaults(default_argv);
267 my_end(verbose ? MY_CHECK_ERROR | MY_GIVE_INFO : MY_CHECK_ERROR);
268 mysql_cond_destroy(&main_thread_keycache_var.suspend);
269 exit(error ? 2 : 0);
270 return 0; /* No compiler warning */
271 }
272
273 enum options_mp {OPT_CHARSETS_DIR_MP=256};
274
275 static struct my_option my_long_options[] =
276 {
277 {"backup", 'b', "Make a backup of the table as table_name.OLD.",
278 &backup, &backup, 0, GET_BOOL, NO_ARG, 0, 0, 0, 0, 0, 0},
279 {"character-sets-dir", OPT_CHARSETS_DIR_MP,
280 "Directory where character sets are.", &charsets_dir,
281 &charsets_dir, 0, GET_STR, REQUIRED_ARG, 0, 0, 0, 0, 0, 0},
282 #ifdef NDEBUG
283 {"debug", '#', "This is a non-debug version. Catch this and exit.",
284 0, 0, 0, GET_DISABLED, OPT_ARG, 0, 0, 0, 0, 0, 0},
285 #else
286 {"debug", '#', "Output debug log. Often this is 'd:t:o,filename'.",
287 0, 0, 0, GET_STR, OPT_ARG, 0, 0, 0, 0, 0, 0},
288 #endif
289 {"force", 'f',
290 "Force packing of table even if it gets bigger or if tempfile exists.",
291 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
292 {"join", 'j',
293 "Join all given tables into 'new_table_name'. All tables MUST have identical layouts.",
294 &join_table, &join_table, 0, GET_STR, REQUIRED_ARG, 0, 0, 0,
295 0, 0, 0},
296 {"help", '?', "Display this help and exit.",
297 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
298 {"silent", 's', "Be more silent.",
299 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
300 {"tmpdir", 'T', "Use temporary directory to store temporary table.",
301 0, 0, 0, GET_STR, REQUIRED_ARG, 0, 0, 0, 0, 0, 0},
302 {"test", 't', "Don't pack table, only test packing it.",
303 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
304 {"verbose", 'v', "Write info about progress and packing result. Use many -v for more verbosity!",
305 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
306 {"version", 'V', "Output version information and exit.",
307 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
308 {"wait", 'w', "Wait and retry if table is in use.", &opt_wait,
309 &opt_wait, 0, GET_BOOL, NO_ARG, 0, 0, 0, 0, 0, 0},
310 { 0, 0, 0, 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0}
311 };
312
313
print_version(void)314 static void print_version(void)
315 {
316 printf("%s Ver 1.23 for %s on %s\n",
317 my_progname, SYSTEM_TYPE, MACHINE_TYPE);
318 }
319
320
usage(void)321 static void usage(void)
322 {
323 print_version();
324 puts(ORACLE_WELCOME_COPYRIGHT_NOTICE("2002"));
325
326 puts("Pack a MyISAM-table to take much less space.");
327 puts("Keys are not updated, you must run myisamchk -rq on the datafile");
328 puts("afterwards to update the keys.");
329 puts("You should give the .MYI file as the filename argument.");
330
331 printf("\nUsage: %s [OPTIONS] filename...\n", my_progname);
332 my_print_help(my_long_options);
333 print_defaults("my", load_default_groups);
334 my_print_variables(my_long_options);
335 }
336
337
338 static my_bool
get_one_option(int optid,const struct my_option * opt MY_ATTRIBUTE ((unused)),char * argument)339 get_one_option(int optid, const struct my_option *opt MY_ATTRIBUTE((unused)),
340 char *argument)
341 {
342 uint length;
343
344 switch(optid) {
345 case 'f':
346 force_pack= 1;
347 tmpfile_createflag= O_RDWR | O_TRUNC;
348 break;
349 case 's':
350 write_loop= verbose= 0;
351 silent= 1;
352 break;
353 case 't':
354 test_only= 1;
355 /* Avoid to reset 'verbose' if it was already set > 1. */
356 if (! verbose)
357 verbose= 1;
358 break;
359 case 'T':
360 length= (uint) (my_stpcpy(tmp_dir, argument) - tmp_dir);
361 if (length != dirname_length(tmp_dir))
362 {
363 tmp_dir[length]=FN_LIBCHAR;
364 tmp_dir[length+1]=0;
365 }
366 break;
367 case 'v':
368 verbose++; /* Allow for selecting the level of verbosity. */
369 silent= 0;
370 break;
371 case '#':
372 DBUG_PUSH(argument ? argument : "d:t:o");
373 break;
374 case 'V':
375 print_version();
376 exit(0);
377 case 'I':
378 case '?':
379 usage();
380 exit(0);
381 }
382 return 0;
383 }
384
385 /* reads options */
386 /* Initiates DEBUG - but no debugging here ! */
387
get_options(int * argc,char *** argv)388 static void get_options(int *argc,char ***argv)
389 {
390 int ho_error;
391
392 my_progname= argv[0][0];
393 if (isatty(fileno(stdout)))
394 write_loop=1;
395
396 if ((ho_error=handle_options(argc, argv, my_long_options, get_one_option)))
397 exit(ho_error);
398
399 if (!*argc)
400 {
401 usage();
402 exit(1);
403 }
404 if (join_table)
405 {
406 backup=0; /* Not needed */
407 tmp_dir[0]=0;
408 }
409 return;
410 }
411
412
open_isam_file(char * name,int mode)413 static MI_INFO *open_isam_file(char *name,int mode)
414 {
415 MI_INFO *isam_file;
416 MYISAM_SHARE *share;
417 DBUG_ENTER("open_isam_file");
418
419 if (!(isam_file=mi_open(name,mode,
420 (opt_wait ? HA_OPEN_WAIT_IF_LOCKED :
421 HA_OPEN_ABORT_IF_LOCKED))))
422 {
423 (void) fprintf(stderr, "%s gave error %d on open\n", name, my_errno());
424 DBUG_RETURN(0);
425 }
426 share=isam_file->s;
427 if (share->options & HA_OPTION_COMPRESS_RECORD && !join_table)
428 {
429 if (!force_pack)
430 {
431 (void) fprintf(stderr, "%s is already compressed\n", name);
432 (void) mi_close(isam_file);
433 DBUG_RETURN(0);
434 }
435 if (verbose)
436 puts("Recompressing already compressed table");
437 share->options&= ~HA_OPTION_READ_ONLY_DATA; /* We are modifing it */
438 }
439 if (! force_pack && share->state.state.records != 0 &&
440 (share->state.state.records <= 1 ||
441 share->state.state.data_file_length < 1024))
442 {
443 (void) fprintf(stderr, "%s is too small to compress\n", name);
444 (void) mi_close(isam_file);
445 DBUG_RETURN(0);
446 }
447 (void) mi_lock_database(isam_file,F_WRLCK);
448 DBUG_RETURN(isam_file);
449 }
450
451
open_isam_files(PACK_MRG_INFO * mrg,char ** names,uint count)452 static my_bool open_isam_files(PACK_MRG_INFO *mrg, char **names, uint count)
453 {
454 uint i,j;
455 mrg->count=0;
456 mrg->current=0;
457 mrg->file=(MI_INFO**) my_malloc(PSI_NOT_INSTRUMENTED,
458 sizeof(MI_INFO*)*count,MYF(MY_FAE));
459 mrg->free_file=1;
460 mrg->src_file_has_indexes_disabled= 0;
461 for (i=0; i < count ; i++)
462 {
463 if (!(mrg->file[i]=open_isam_file(names[i],O_RDONLY)))
464 goto error;
465
466 mrg->src_file_has_indexes_disabled|=
467 ! mi_is_all_keys_active(mrg->file[i]->s->state.key_map,
468 mrg->file[i]->s->base.keys);
469 }
470 /* Check that files are identical */
471 for (j=0 ; j < count-1 ; j++)
472 {
473 MI_COLUMNDEF *m1,*m2,*end;
474 if (mrg->file[j]->s->base.reclength != mrg->file[j+1]->s->base.reclength ||
475 mrg->file[j]->s->base.fields != mrg->file[j+1]->s->base.fields)
476 goto diff_file;
477 m1=mrg->file[j]->s->rec;
478 end=m1+mrg->file[j]->s->base.fields;
479 m2=mrg->file[j+1]->s->rec;
480 for ( ; m1 != end ; m1++,m2++)
481 {
482 if (m1->type != m2->type || m1->length != m2->length)
483 goto diff_file;
484 }
485 }
486 mrg->count=count;
487 return 0;
488
489 diff_file:
490 (void) fprintf(stderr, "%s: Tables '%s' and '%s' are not identical\n",
491 my_progname, names[j], names[j+1]);
492 error:
493 while (i--)
494 mi_close(mrg->file[i]);
495 my_free(mrg->file);
496 return 1;
497 }
498
499
compress(PACK_MRG_INFO * mrg,char * result_table)500 static int compress(PACK_MRG_INFO *mrg,char *result_table)
501 {
502 int error;
503 File new_file,join_isam_file;
504 MI_INFO *isam_file;
505 MYISAM_SHARE *share;
506 char org_name[FN_REFLEN],new_name[FN_REFLEN],temp_name[FN_REFLEN];
507 uint i,header_length,fields,trees,used_trees;
508 my_off_t old_length,new_length,tot_elements;
509 HUFF_COUNTS *huff_counts;
510 HUFF_TREE *huff_trees;
511 DBUG_ENTER("compress");
512
513 isam_file=mrg->file[0]; /* Take this as an example */
514 share=isam_file->s;
515 new_file=join_isam_file= -1;
516 trees=fields=0;
517 huff_trees=0;
518 huff_counts=0;
519
520 /* Create temporary or join file */
521
522 if (backup)
523 (void) fn_format(org_name,isam_file->filename,"",MI_NAME_DEXT,2);
524 else
525 (void) fn_format(org_name,isam_file->filename,"",MI_NAME_DEXT,2+4+16);
526 if (!test_only && result_table)
527 {
528 /* Make a new indexfile based on first file in list */
529 uint length;
530 uchar *buff;
531 my_stpcpy(org_name,result_table); /* Fix error messages */
532 (void) fn_format(new_name,result_table,"",MI_NAME_IEXT,2);
533 if ((join_isam_file=my_create(new_name,0,tmpfile_createflag,MYF(MY_WME)))
534 < 0)
535 goto err;
536 length=(uint) share->base.keystart;
537 if (!(buff= (uchar*) my_malloc(PSI_NOT_INSTRUMENTED,
538 length,MYF(MY_WME))))
539 goto err;
540 if (my_pread(share->kfile,buff,length,0L,MYF(MY_WME | MY_NABP)) ||
541 my_write(join_isam_file,buff,length,
542 MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)))
543 {
544 my_free(buff);
545 goto err;
546 }
547 my_free(buff);
548 (void) fn_format(new_name,result_table,"",MI_NAME_DEXT,2);
549 }
550 else if (!tmp_dir[0])
551 (void) make_new_name(new_name,org_name);
552 else
553 (void) fn_format(new_name,org_name,tmp_dir,DATA_TMP_EXT,1+2+4);
554 if (!test_only &&
555 (new_file=my_create(new_name,0,tmpfile_createflag,MYF(MY_WME))) < 0)
556 goto err;
557
558 /* Start calculating statistics */
559
560 mrg->records=0;
561 for (i=0 ; i < mrg->count ; i++)
562 mrg->records+=mrg->file[i]->s->state.state.records;
563
564 DBUG_PRINT("info", ("Compressing %s: (%lu records)",
565 result_table ? new_name : org_name,
566 (ulong) mrg->records));
567 if (write_loop || verbose)
568 {
569 printf("Compressing %s: (%lu records)\n",
570 result_table ? new_name : org_name, (ulong) mrg->records);
571 }
572 trees=fields=share->base.fields;
573 huff_counts=init_huff_count(isam_file,mrg->records);
574
575 /*
576 Read the whole data file(s) for statistics.
577 */
578 DBUG_PRINT("info", ("- Calculating statistics"));
579 if (write_loop || verbose)
580 printf("- Calculating statistics\n");
581 if (get_statistic(mrg,huff_counts))
582 goto err;
583
584 old_length=0;
585 for (i=0; i < mrg->count ; i++)
586 old_length+= (mrg->file[i]->s->state.state.data_file_length -
587 mrg->file[i]->s->state.state.empty);
588
589 /*
590 Create a global priority queue in preparation for making
591 temporary Huffman trees.
592 */
593 if (init_queue(&queue,256,0,0,compare_huff_elements,0))
594 goto err;
595
596 /*
597 Check each column if we should use pre-space-compress, end-space-
598 compress, empty-field-compress or zero-field-compress.
599 */
600 check_counts(huff_counts,fields,mrg->records);
601
602 /*
603 Build a Huffman tree for each column.
604 */
605 huff_trees=make_huff_trees(huff_counts,trees);
606
607 /*
608 If the packed lengths of combined columns is less then the sum of
609 the non-combined columns, then create common Huffman trees for them.
610 We do this only for byte compressed columns, not for distinct values
611 compressed columns.
612 */
613 if ((int) (used_trees=join_same_trees(huff_counts,trees)) < 0)
614 goto err;
615
616 /*
617 Assign codes to all byte or column values.
618 */
619 if (make_huff_decode_table(huff_trees,fields))
620 goto err;
621
622 /* Prepare a file buffer. */
623 init_file_buffer(new_file,0);
624
625 /*
626 Reserve space in the target file for the fixed compressed file header.
627 */
628 file_buffer.pos_in_file=HEAD_LENGTH;
629 if (! test_only)
630 my_seek(new_file,file_buffer.pos_in_file,MY_SEEK_SET,MYF(0));
631
632 /*
633 Write field infos: field type, pack type, length bits, tree number.
634 */
635 write_field_info(huff_counts,fields,used_trees);
636
637 /*
638 Write decode trees.
639 */
640 if (!(tot_elements=write_huff_tree(huff_trees,trees)))
641 goto err;
642
643 /*
644 Calculate the total length of the compression info header.
645 This includes the fixed compressed file header, the column compression
646 type descriptions, and the decode trees.
647 */
648 header_length=(uint) file_buffer.pos_in_file+
649 (uint) (file_buffer.pos-file_buffer.buffer);
650
651 /*
652 Compress the source file into the target file.
653 */
654 DBUG_PRINT("info", ("- Compressing file"));
655 if (write_loop || verbose)
656 printf("- Compressing file\n");
657 error=compress_isam_file(mrg,huff_counts);
658 new_length=file_buffer.pos_in_file;
659 if (!error && !test_only)
660 {
661 uchar buff[MEMMAP_EXTRA_MARGIN]; /* End marginal for memmap */
662 memset(buff, 0, sizeof(buff));
663 error=my_write(file_buffer.file,buff,sizeof(buff),
664 MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)) != 0;
665 }
666
667 /*
668 Write the fixed compressed file header.
669 */
670 if (!error)
671 error=write_header(mrg,header_length,used_trees,tot_elements,
672 new_length);
673
674 /* Flush the file buffer. */
675 end_file_buffer();
676
677 /* Display statistics. */
678 DBUG_PRINT("info", ("Min record length: %6d Max length: %6d "
679 "Mean total length: %6ld\n",
680 mrg->min_pack_length, mrg->max_pack_length,
681 (ulong) (mrg->records ? (new_length/mrg->records) : 0)));
682 if (verbose && mrg->records)
683 printf("Min record length: %6d Max length: %6d "
684 "Mean total length: %6ld\n", mrg->min_pack_length,
685 mrg->max_pack_length, (ulong) (new_length/mrg->records));
686
687 /* Close source and target file. */
688 if (!test_only)
689 {
690 error|=my_close(new_file,MYF(MY_WME));
691 if (!result_table)
692 {
693 error|=my_close(isam_file->dfile,MYF(MY_WME));
694 isam_file->dfile= -1; /* Tell mi_close file is closed */
695 }
696 }
697
698 /* Cleanup. */
699 free_counts_and_tree_and_queue(huff_trees,trees,huff_counts,fields);
700 if (! test_only && ! error)
701 {
702 if (result_table)
703 {
704 error=save_state_mrg(join_isam_file,mrg,new_length,glob_crc);
705 }
706 else
707 {
708 if (backup)
709 {
710 if (my_rename(org_name,make_old_name(temp_name,isam_file->filename),
711 MYF(MY_WME)))
712 error=1;
713 else
714 {
715 if (tmp_dir[0])
716 error=my_copy(new_name,org_name,MYF(MY_WME));
717 else
718 error=my_rename(new_name,org_name,MYF(MY_WME));
719 if (!error)
720 {
721 (void) my_copystat(temp_name,org_name,MYF(MY_COPYTIME));
722 if (tmp_dir[0])
723 (void) my_delete(new_name,MYF(MY_WME));
724 }
725 }
726 }
727 else
728 {
729 if (tmp_dir[0])
730 {
731 error=my_copy(new_name,org_name,
732 MYF(MY_WME | MY_HOLD_ORIGINAL_MODES | MY_COPYTIME));
733 if (!error)
734 (void) my_delete(new_name,MYF(MY_WME));
735 }
736 else
737 error=my_redel(org_name,new_name,MYF(MY_WME | MY_COPYTIME));
738 }
739 if (! error)
740 error=save_state(isam_file,mrg,new_length,glob_crc);
741 }
742 }
743 error|=mrg_close(mrg);
744 if (join_isam_file >= 0)
745 error|=my_close(join_isam_file,MYF(MY_WME));
746 if (error)
747 {
748 (void) fprintf(stderr, "Aborting: %s is not compressed\n", org_name);
749 (void) my_delete(new_name,MYF(MY_WME));
750 DBUG_RETURN(-1);
751 }
752 if (write_loop || verbose)
753 {
754 if (old_length)
755 printf("%.4g%% \n",
756 (((longlong) (old_length - new_length)) * 100.0 /
757 (longlong) old_length));
758 else
759 puts("Empty file saved in compressed format");
760 }
761 DBUG_RETURN(0);
762
763 err:
764 free_counts_and_tree_and_queue(huff_trees,trees,huff_counts,fields);
765 if (new_file >= 0)
766 (void) my_close(new_file,MYF(0));
767 if (join_isam_file >= 0)
768 (void) my_close(join_isam_file,MYF(0));
769 mrg_close(mrg);
770 (void) fprintf(stderr, "Aborted: %s is not compressed\n", org_name);
771 DBUG_RETURN(-1);
772 }
773
774
775 /**
776 Create FRM for the destination table for --join operation
777 Copy the first table FRM as the destination table FRM file. Doing so
778 will help the mysql server to recognize the newly created table.
779 See Bug#36573.
780
781 @param source_table Name of the source table
782 @param dest_table Name of the destination table
783 @retval 0 Successful copy operation
784
785 @note We always return 0 because we don't want myisampack to report error
786 even if the copy operation fails.
787 */
788
create_dest_frm(char * source_table,char * dest_table)789 static int create_dest_frm(char *source_table, char *dest_table)
790 {
791 char source_name[FN_REFLEN], dest_name[FN_REFLEN];
792
793 DBUG_ENTER("create_dest_frm");
794
795 (void) fn_format(source_name, source_table,
796 "", FRM_EXT, MY_UNPACK_FILENAME | MY_RESOLVE_SYMLINKS);
797 (void) fn_format(dest_name, dest_table,
798 "", FRM_EXT, MY_UNPACK_FILENAME | MY_RESOLVE_SYMLINKS);
799 /*
800 Error messages produced by my_copy() are suppressed as this
801 is not vital for --join operation. User shouldn't see any error messages
802 like "source file frm not found" and "unable to create destination frm
803 file. So we don't pass the flag MY_WME -Write Message on Error to
804 my_copy()
805 */
806 (void) my_copy(source_name, dest_name, MYF(MY_DONT_OVERWRITE_FILE));
807
808 DBUG_RETURN(0);
809 }
810
811
812 /* Init a huff_count-struct for each field and init it */
813
init_huff_count(MI_INFO * info,my_off_t records)814 static HUFF_COUNTS *init_huff_count(MI_INFO *info,my_off_t records)
815 {
816 uint i;
817 HUFF_COUNTS *count;
818 if ((count = (HUFF_COUNTS*) my_malloc(PSI_NOT_INSTRUMENTED,
819 info->s->base.fields*
820 sizeof(HUFF_COUNTS),
821 MYF(MY_ZEROFILL | MY_WME))))
822 {
823 for (i=0 ; i < info->s->base.fields ; i++)
824 {
825 enum en_fieldtype type;
826 count[i].field_length=info->s->rec[i].length;
827 type= count[i].field_type= (enum en_fieldtype) info->s->rec[i].type;
828 if (type == FIELD_INTERVALL ||
829 type == FIELD_CONSTANT ||
830 type == FIELD_ZERO)
831 type = FIELD_NORMAL;
832 if (count[i].field_length <= 8 &&
833 (type == FIELD_NORMAL ||
834 type == FIELD_SKIP_ZERO))
835 count[i].max_zero_fill= count[i].field_length;
836 /*
837 For every column initialize a tree, which is used to detect distinct
838 column values. 'int_tree' works together with 'tree_buff' and
839 'tree_pos'. It's keys are implemented by pointers into 'tree_buff'.
840 This is accomplished by '-1' as the element size.
841 */
842 init_tree(&count[i].int_tree,0,0,-1,(qsort_cmp2) compare_tree,0, NULL,
843 NULL);
844 if (records && type != FIELD_BLOB && type != FIELD_VARCHAR)
845 count[i].tree_pos=count[i].tree_buff =
846 my_malloc(PSI_NOT_INSTRUMENTED,
847 count[i].field_length > 1 ? tree_buff_length : 2,
848 MYF(MY_WME));
849 }
850 }
851 return count;
852 }
853
854
855 /* Free memory used by counts and trees */
856
free_counts_and_tree_and_queue(HUFF_TREE * huff_trees,uint trees,HUFF_COUNTS * huff_counts,uint fields)857 static void free_counts_and_tree_and_queue(HUFF_TREE *huff_trees, uint trees,
858 HUFF_COUNTS *huff_counts,
859 uint fields)
860 {
861 uint i;
862
863 if (huff_trees)
864 {
865 for (i=0 ; i < trees ; i++)
866 {
867 if (huff_trees[i].element_buffer)
868 my_free(huff_trees[i].element_buffer);
869 if (huff_trees[i].code)
870 my_free(huff_trees[i].code);
871 }
872 my_free(huff_trees);
873 }
874 if (huff_counts)
875 {
876 for (i=0 ; i < fields ; i++)
877 {
878 if (huff_counts[i].tree_buff)
879 {
880 my_free(huff_counts[i].tree_buff);
881 delete_tree(&huff_counts[i].int_tree);
882 }
883 }
884 my_free(huff_counts);
885 }
886 delete_queue(&queue); /* This is safe to free */
887 return;
888 }
889
890 /* Read through old file and gather some statistics */
891
get_statistic(PACK_MRG_INFO * mrg,HUFF_COUNTS * huff_counts)892 static int get_statistic(PACK_MRG_INFO *mrg,HUFF_COUNTS *huff_counts)
893 {
894 int error;
895 uint length;
896 ulong reclength,max_blob_length;
897 uchar *record,*pos,*next_pos,*end_pos,*start_pos;
898 ha_rows record_count;
899 my_bool static_row_size;
900 HUFF_COUNTS *count,*end_count;
901 TREE_ELEMENT *element;
902 DBUG_ENTER("get_statistic");
903
904 reclength=mrg->file[0]->s->base.reclength;
905 record=(uchar*) my_alloca(reclength);
906 end_count=huff_counts+mrg->file[0]->s->base.fields;
907 record_count=0; glob_crc=0;
908 max_blob_length=0;
909
910 /* Check how to calculate checksum */
911 static_row_size=1;
912 for (count=huff_counts ; count < end_count ; count++)
913 {
914 if (count->field_type == FIELD_BLOB ||
915 count->field_type == FIELD_VARCHAR)
916 {
917 static_row_size=0;
918 break;
919 }
920 }
921
922 mrg_reset(mrg);
923 while ((error=mrg_rrnd(mrg,record)) != HA_ERR_END_OF_FILE)
924 {
925 ulong tot_blob_length=0;
926 if (! error)
927 {
928 /* glob_crc is a checksum over all bytes of all records. */
929 if (static_row_size)
930 glob_crc+=mi_static_checksum(mrg->file[0],record);
931 else
932 glob_crc+=mi_checksum(mrg->file[0],record);
933
934 /* Count the incidence of values separately for every column. */
935 for (pos=record,count=huff_counts ;
936 count < end_count ;
937 count++,
938 pos=next_pos)
939 {
940 next_pos=end_pos=(start_pos=pos)+count->field_length;
941
942 /*
943 Put the whole column value in a tree if there is room for it.
944 'int_tree' is used to quickly check for duplicate values.
945 'tree_buff' collects as many distinct column values as
946 possible. If the field length is > 1, it is tree_buff_length,
947 else 2 bytes. Each value is 'field_length' bytes big. If there
948 are more distinct column values than fit into the buffer, we
949 give up with this tree. BLOBs and VARCHARs do not have a
950 tree_buff as it can only be used with fixed length columns.
951 For the special case of field length == 1, we handle only the
952 case that there is only one distinct value in the table(s).
953 Otherwise, we can have a maximum of 256 distinct values. This
954 is then handled by the normal Huffman tree build.
955
956 Another limit for collecting distinct column values is the
957 number of values itself. Since we would need to build a
958 Huffman tree for the values, we are limited by the 'IS_OFFSET'
959 constant. This constant expresses a bit which is used to
960 determine if a tree element holds a final value or an offset
961 to a child element. Hence, all values and offsets need to be
962 smaller than 'IS_OFFSET'. A tree element is implemented with
963 two integer values, one for the left branch and one for the
964 right branch. For the extreme case that the first element
965 points to the last element, the number of integers in the tree
966 must be less or equal to IS_OFFSET. So the number of elements
967 must be less or equal to IS_OFFSET / 2.
968
969 WARNING: At first, we insert a pointer into the record buffer
970 as the key for the tree. If we got a new distinct value, which
971 is really inserted into the tree, instead of being counted
972 only, we will copy the column value from the record buffer to
973 'tree_buff' and adjust the key pointer of the tree accordingly.
974 */
975 if (count->tree_buff)
976 {
977 global_count=count;
978 if (!(element=tree_insert(&count->int_tree,pos, 0,
979 count->int_tree.custom_arg)) ||
980 (element->count == 1 &&
981 (count->tree_buff + tree_buff_length <
982 count->tree_pos + count->field_length)) ||
983 (count->int_tree.elements_in_tree > IS_OFFSET / 2) ||
984 (count->field_length == 1 &&
985 count->int_tree.elements_in_tree > 1))
986 {
987 delete_tree(&count->int_tree);
988 my_free(count->tree_buff);
989 count->tree_buff=0;
990 }
991 else
992 {
993 /*
994 If tree_insert() succeeds, it either creates a new element
995 or increments the counter of an existing element.
996 */
997 if (element->count == 1)
998 {
999 /* Copy the new column value into 'tree_buff'. */
1000 memcpy(count->tree_pos,pos,(size_t) count->field_length);
1001 /* Adjust the key pointer in the tree. */
1002 tree_set_pointer(element,count->tree_pos);
1003 /* Point behind the last column value so far. */
1004 count->tree_pos+=count->field_length;
1005 }
1006 }
1007 }
1008
1009 /* Save character counters and space-counts and zero-field-counts */
1010 if (count->field_type == FIELD_NORMAL ||
1011 count->field_type == FIELD_SKIP_ENDSPACE)
1012 {
1013 /* Ignore trailing space. */
1014 for ( ; end_pos > pos ; end_pos--)
1015 if (end_pos[-1] != ' ')
1016 break;
1017 /* Empty fields are just counted. Go to the next record. */
1018 if (end_pos == pos)
1019 {
1020 count->empty_fields++;
1021 count->max_zero_fill=0;
1022 continue;
1023 }
1024 /*
1025 Count the total of all trailing spaces and the number of
1026 short trailing spaces. Remember the longest trailing space.
1027 */
1028 length= (uint) (next_pos-end_pos);
1029 count->tot_end_space+=length;
1030 if (length < 8)
1031 count->end_space[length]++;
1032 if (count->max_end_space < length)
1033 count->max_end_space = length;
1034 }
1035
1036 if (count->field_type == FIELD_NORMAL ||
1037 count->field_type == FIELD_SKIP_PRESPACE)
1038 {
1039 /* Ignore leading space. */
1040 for (pos=start_pos; pos < end_pos ; pos++)
1041 if (pos[0] != ' ')
1042 break;
1043 /* Empty fields are just counted. Go to the next record. */
1044 if (end_pos == pos)
1045 {
1046 count->empty_fields++;
1047 count->max_zero_fill=0;
1048 continue;
1049 }
1050 /*
1051 Count the total of all leading spaces and the number of
1052 short leading spaces. Remember the longest leading space.
1053 */
1054 length= (uint) (pos-start_pos);
1055 count->tot_pre_space+=length;
1056 if (length < 8)
1057 count->pre_space[length]++;
1058 if (count->max_pre_space < length)
1059 count->max_pre_space = length;
1060 }
1061
1062 /* Calculate pos, end_pos, and max_length for variable length fields. */
1063 if (count->field_type == FIELD_BLOB)
1064 {
1065 uint field_length=count->field_length -portable_sizeof_char_ptr;
1066 ulong blob_length= _mi_calc_blob_length(field_length, start_pos);
1067 memcpy(&pos, start_pos+field_length, sizeof(char*));
1068 end_pos=pos+blob_length;
1069 tot_blob_length+=blob_length;
1070 set_if_bigger(count->max_length,blob_length);
1071 }
1072 else if (count->field_type == FIELD_VARCHAR)
1073 {
1074 uint pack_length= HA_VARCHAR_PACKLENGTH(count->field_length-1);
1075 length= (pack_length == 1 ? (uint) *(uchar*) start_pos :
1076 uint2korr(start_pos));
1077 pos= start_pos+pack_length;
1078 end_pos= pos+length;
1079 set_if_bigger(count->max_length,length);
1080 }
1081
1082 /* Evaluate 'max_zero_fill' for short fields. */
1083 if (count->field_length <= 8 &&
1084 (count->field_type == FIELD_NORMAL ||
1085 count->field_type == FIELD_SKIP_ZERO))
1086 {
1087 uint i;
1088 /* Zero fields are just counted. Go to the next record. */
1089 if (!memcmp((uchar*) start_pos,zero_string,count->field_length))
1090 {
1091 count->zero_fields++;
1092 continue;
1093 }
1094 /*
1095 max_zero_fill starts with field_length. It is decreased every
1096 time a shorter "zero trailer" is found. It is set to zero when
1097 an empty field is found (see above). This suggests that the
1098 variable should be called 'min_zero_fill'.
1099 */
1100 for (i =0 ; i < count->max_zero_fill && ! end_pos[-1 - (int) i] ;
1101 i++) ;
1102 if (i < count->max_zero_fill)
1103 count->max_zero_fill=i;
1104 }
1105
1106 /* Ignore zero fields and check fields. */
1107 if (count->field_type == FIELD_ZERO ||
1108 count->field_type == FIELD_CHECK)
1109 continue;
1110
1111 /*
1112 Count the incidence of every byte value in the
1113 significant field value.
1114 */
1115 for ( ; pos < end_pos ; pos++)
1116 count->counts[(uchar) *pos]++;
1117
1118 /* Step to next field. */
1119 }
1120
1121 if (tot_blob_length > max_blob_length)
1122 max_blob_length=tot_blob_length;
1123 record_count++;
1124 if (write_loop && record_count % WRITE_COUNT == 0)
1125 {
1126 printf("%lu\r", (ulong) record_count);
1127 (void) fflush(stdout);
1128 }
1129 }
1130 else if (error != HA_ERR_RECORD_DELETED)
1131 {
1132 (void) fprintf(stderr, "Got error %d while reading rows", error);
1133 break;
1134 }
1135
1136 /* Step to next record. */
1137 }
1138 if (write_loop)
1139 {
1140 printf(" \r");
1141 (void) fflush(stdout);
1142 }
1143
1144 /*
1145 If --debug=d,fakebigcodes is set, fake the counts to get big Huffman
1146 codes.
1147 */
1148 DBUG_EXECUTE_IF("fakebigcodes", fakebigcodes(huff_counts, end_count););
1149
1150 DBUG_PRINT("info", ("Found the following number of incidents "
1151 "of the byte codes:"));
1152 if (verbose >= 2)
1153 printf("Found the following number of incidents "
1154 "of the byte codes:\n");
1155 for (count= huff_counts ; count < end_count; count++)
1156 {
1157 uint idx;
1158 my_off_t total_count;
1159 char llbuf[32];
1160
1161 DBUG_PRINT("info", ("column: %3u", (uint) (count - huff_counts + 1)));
1162 if (verbose >= 2)
1163 printf("column: %3u\n", (uint) (count - huff_counts + 1));
1164 if (count->tree_buff)
1165 {
1166 DBUG_PRINT("info", ("number of distinct values: %u",
1167 (uint) ((count->tree_pos - count->tree_buff) /
1168 count->field_length)));
1169 if (verbose >= 2)
1170 printf("number of distinct values: %u\n",
1171 (uint) ((count->tree_pos - count->tree_buff) /
1172 count->field_length));
1173 }
1174 total_count= 0;
1175 for (idx= 0; idx < 256; idx++)
1176 {
1177 if (count->counts[idx])
1178 {
1179 total_count+= count->counts[idx];
1180 DBUG_PRINT("info", ("counts[0x%02x]: %12s", idx,
1181 llstr((longlong) count->counts[idx], llbuf)));
1182 if (verbose >= 2)
1183 printf("counts[0x%02x]: %12s\n", idx,
1184 llstr((longlong) count->counts[idx], llbuf));
1185 }
1186 }
1187 DBUG_PRINT("info", ("total: %12s", llstr((longlong) total_count,
1188 llbuf)));
1189 if ((verbose >= 2) && total_count)
1190 {
1191 printf("total: %12s\n",
1192 llstr((longlong) total_count, llbuf));
1193 }
1194 }
1195
1196 mrg->records=record_count;
1197 mrg->max_blob_length=max_blob_length;
1198 DBUG_RETURN(error != HA_ERR_END_OF_FILE);
1199 }
1200
compare_huff_elements(void * not_used MY_ATTRIBUTE ((unused)),uchar * a,uchar * b)1201 static int compare_huff_elements(void *not_used MY_ATTRIBUTE((unused)),
1202 uchar *a, uchar *b)
1203 {
1204 return *((my_off_t*) a) < *((my_off_t*) b) ? -1 :
1205 (*((my_off_t*) a) == *((my_off_t*) b) ? 0 : 1);
1206 }
1207
1208 /* Check each tree if we should use pre-space-compress, end-space-
1209 compress, empty-field-compress or zero-field-compress */
1210
check_counts(HUFF_COUNTS * huff_counts,uint trees,my_off_t records)1211 static void check_counts(HUFF_COUNTS *huff_counts, uint trees,
1212 my_off_t records)
1213 {
1214 uint space_fields,fill_zero_fields,field_count[(int) FIELD_enum_val_count];
1215 my_off_t old_length,new_length,length;
1216 DBUG_ENTER("check_counts");
1217
1218 memset(field_count, 0, sizeof(field_count));
1219 space_fields=fill_zero_fields=0;
1220
1221 for (; trees-- ; huff_counts++)
1222 {
1223 if (huff_counts->field_type == FIELD_BLOB)
1224 {
1225 huff_counts->length_bits=max_bit(huff_counts->max_length);
1226 goto found_pack;
1227 }
1228 else if (huff_counts->field_type == FIELD_VARCHAR)
1229 {
1230 huff_counts->length_bits=max_bit(huff_counts->max_length);
1231 goto found_pack;
1232 }
1233 else if (huff_counts->field_type == FIELD_CHECK)
1234 {
1235 huff_counts->bytes_packed=0;
1236 huff_counts->counts[0]=0;
1237 goto found_pack;
1238 }
1239
1240 huff_counts->field_type=FIELD_NORMAL;
1241 huff_counts->pack_type=0;
1242
1243 /* Check for zero-filled records (in this column), or zero records. */
1244 if (huff_counts->zero_fields || ! records)
1245 {
1246 my_off_t old_space_count;
1247 /*
1248 If there are only zero filled records (in this column),
1249 or no records at all, we are done.
1250 */
1251 if (huff_counts->zero_fields == records)
1252 {
1253 huff_counts->field_type= FIELD_ZERO;
1254 huff_counts->bytes_packed=0;
1255 huff_counts->counts[0]=0;
1256 goto found_pack;
1257 }
1258 /* Remeber the number of significant spaces. */
1259 old_space_count=huff_counts->counts[' '];
1260 /* Add all leading and trailing spaces. */
1261 huff_counts->counts[' ']+= (huff_counts->tot_end_space +
1262 huff_counts->tot_pre_space +
1263 huff_counts->empty_fields *
1264 huff_counts->field_length);
1265 /* Check, what the compressed length of this would be. */
1266 old_length=calc_packed_length(huff_counts,0)+records/8;
1267 /* Get the number of zero bytes. */
1268 length=huff_counts->zero_fields*huff_counts->field_length;
1269 /* Add it to the counts. */
1270 huff_counts->counts[0]+=length;
1271 /* Check, what the compressed length of this would be. */
1272 new_length=calc_packed_length(huff_counts,0);
1273 /* If the compression without the zeroes would be shorter, we are done. */
1274 if (old_length < new_length && huff_counts->field_length > 1)
1275 {
1276 huff_counts->field_type=FIELD_SKIP_ZERO;
1277 huff_counts->counts[0]-=length;
1278 huff_counts->bytes_packed=old_length- records/8;
1279 goto found_pack;
1280 }
1281 /* Remove the insignificant spaces, but keep the zeroes. */
1282 huff_counts->counts[' ']=old_space_count;
1283 }
1284 /* Check, what the compressed length of this column would be. */
1285 huff_counts->bytes_packed=calc_packed_length(huff_counts,0);
1286
1287 /*
1288 If there are enough empty records (in this column),
1289 treating them specially may pay off.
1290 */
1291 if (huff_counts->empty_fields)
1292 {
1293 if (huff_counts->field_length > 2 &&
1294 huff_counts->empty_fields + (records - huff_counts->empty_fields)*
1295 (1+max_bit(MY_MAX(huff_counts->max_pre_space,
1296 huff_counts->max_end_space))) <
1297 records * max_bit(huff_counts->field_length))
1298 {
1299 huff_counts->pack_type |= PACK_TYPE_SPACE_FIELDS;
1300 }
1301 else
1302 {
1303 length=huff_counts->empty_fields*huff_counts->field_length;
1304 if (huff_counts->tot_end_space || ! huff_counts->tot_pre_space)
1305 {
1306 huff_counts->tot_end_space+=length;
1307 huff_counts->max_end_space=huff_counts->field_length;
1308 if (huff_counts->field_length < 8)
1309 huff_counts->end_space[huff_counts->field_length]+=
1310 huff_counts->empty_fields;
1311 }
1312 if (huff_counts->tot_pre_space)
1313 {
1314 huff_counts->tot_pre_space+=length;
1315 huff_counts->max_pre_space=huff_counts->field_length;
1316 if (huff_counts->field_length < 8)
1317 huff_counts->pre_space[huff_counts->field_length]+=
1318 huff_counts->empty_fields;
1319 }
1320 }
1321 }
1322
1323 /*
1324 If there are enough trailing spaces (in this column),
1325 treating them specially may pay off.
1326 */
1327 if (huff_counts->tot_end_space)
1328 {
1329 huff_counts->counts[' ']+=huff_counts->tot_pre_space;
1330 if (test_space_compress(huff_counts,records,huff_counts->max_end_space,
1331 huff_counts->end_space,
1332 huff_counts->tot_end_space,FIELD_SKIP_ENDSPACE))
1333 goto found_pack;
1334 huff_counts->counts[' ']-=huff_counts->tot_pre_space;
1335 }
1336
1337 /*
1338 If there are enough leading spaces (in this column),
1339 treating them specially may pay off.
1340 */
1341 if (huff_counts->tot_pre_space)
1342 {
1343 if (test_space_compress(huff_counts,records,huff_counts->max_pre_space,
1344 huff_counts->pre_space,
1345 huff_counts->tot_pre_space,FIELD_SKIP_PRESPACE))
1346 goto found_pack;
1347 }
1348
1349 found_pack: /* Found field-packing */
1350
1351 /* Test if we can use zero-fill */
1352
1353 if (huff_counts->max_zero_fill &&
1354 (huff_counts->field_type == FIELD_NORMAL ||
1355 huff_counts->field_type == FIELD_SKIP_ZERO))
1356 {
1357 huff_counts->counts[0]-=huff_counts->max_zero_fill*
1358 (huff_counts->field_type == FIELD_SKIP_ZERO ?
1359 records - huff_counts->zero_fields : records);
1360 huff_counts->pack_type|=PACK_TYPE_ZERO_FILL;
1361 huff_counts->bytes_packed=calc_packed_length(huff_counts,0);
1362 }
1363
1364 /* Test if intervall-field is better */
1365
1366 if (huff_counts->tree_buff)
1367 {
1368 HUFF_TREE tree;
1369
1370 DBUG_EXECUTE_IF("forceintervall",
1371 huff_counts->bytes_packed= ~ (my_off_t) 0;);
1372 tree.element_buffer=0;
1373 if (!make_huff_tree(&tree,huff_counts) &&
1374 tree.bytes_packed+tree.tree_pack_length < huff_counts->bytes_packed)
1375 {
1376 if (tree.elements == 1)
1377 huff_counts->field_type=FIELD_CONSTANT;
1378 else
1379 huff_counts->field_type=FIELD_INTERVALL;
1380 huff_counts->pack_type=0;
1381 }
1382 else
1383 {
1384 my_free(huff_counts->tree_buff);
1385 delete_tree(&huff_counts->int_tree);
1386 huff_counts->tree_buff=0;
1387 }
1388 if (tree.element_buffer)
1389 my_free(tree.element_buffer);
1390 }
1391 if (huff_counts->pack_type & PACK_TYPE_SPACE_FIELDS)
1392 space_fields++;
1393 if (huff_counts->pack_type & PACK_TYPE_ZERO_FILL)
1394 fill_zero_fields++;
1395 field_count[huff_counts->field_type]++;
1396 }
1397 DBUG_PRINT("info", ("normal: %3d empty-space: %3d "
1398 "empty-zero: %3d empty-fill: %3d",
1399 field_count[FIELD_NORMAL],space_fields,
1400 field_count[FIELD_SKIP_ZERO],fill_zero_fields));
1401 DBUG_PRINT("info", ("pre-space: %3d end-space: %3d "
1402 "intervall-fields: %3d zero: %3d",
1403 field_count[FIELD_SKIP_PRESPACE],
1404 field_count[FIELD_SKIP_ENDSPACE],
1405 field_count[FIELD_INTERVALL],
1406 field_count[FIELD_ZERO]));
1407 if (verbose)
1408 printf("\nnormal: %3d empty-space: %3d "
1409 "empty-zero: %3d empty-fill: %3d\n"
1410 "pre-space: %3d end-space: %3d "
1411 "intervall-fields: %3d zero: %3d\n",
1412 field_count[FIELD_NORMAL],space_fields,
1413 field_count[FIELD_SKIP_ZERO],fill_zero_fields,
1414 field_count[FIELD_SKIP_PRESPACE],
1415 field_count[FIELD_SKIP_ENDSPACE],
1416 field_count[FIELD_INTERVALL],
1417 field_count[FIELD_ZERO]);
1418 DBUG_VOID_RETURN;
1419 }
1420
1421 /* Test if we can use space-compression and empty-field-compression */
1422
1423 static int
test_space_compress(HUFF_COUNTS * huff_counts,my_off_t records,uint max_space_length,my_off_t * space_counts,my_off_t tot_space_count,enum en_fieldtype field_type)1424 test_space_compress(HUFF_COUNTS *huff_counts, my_off_t records,
1425 uint max_space_length, my_off_t *space_counts,
1426 my_off_t tot_space_count, enum en_fieldtype field_type)
1427 {
1428 int min_pos;
1429 uint length_bits,i;
1430 my_off_t space_count,min_space_count,min_pack,new_length,skip;
1431
1432 length_bits=max_bit(max_space_length);
1433
1434 /* Default no end_space-packing */
1435 space_count=huff_counts->counts[(uint) ' '];
1436 min_space_count= (huff_counts->counts[(uint) ' ']+= tot_space_count);
1437 min_pack=calc_packed_length(huff_counts,0);
1438 min_pos= -2;
1439 huff_counts->counts[(uint) ' ']=space_count;
1440
1441 /* Test with allways space-count */
1442 new_length=huff_counts->bytes_packed+length_bits*records/8;
1443 if (new_length+1 < min_pack)
1444 {
1445 min_pos= -1;
1446 min_pack=new_length;
1447 min_space_count=space_count;
1448 }
1449 /* Test with length-flag */
1450 for (skip=0L, i=0 ; i < 8 ; i++)
1451 {
1452 if (space_counts[i])
1453 {
1454 if (i)
1455 huff_counts->counts[(uint) ' ']+=space_counts[i];
1456 skip+=huff_counts->pre_space[i];
1457 new_length=calc_packed_length(huff_counts,0)+
1458 (records+(records-skip)*(1+length_bits))/8;
1459 if (new_length < min_pack)
1460 {
1461 min_pos=(int) i;
1462 min_pack=new_length;
1463 min_space_count=huff_counts->counts[(uint) ' '];
1464 }
1465 }
1466 }
1467
1468 huff_counts->counts[(uint) ' ']=min_space_count;
1469 huff_counts->bytes_packed=min_pack;
1470 switch (min_pos) {
1471 case -2:
1472 return(0); /* No space-compress */
1473 case -1: /* Always space-count */
1474 huff_counts->field_type=field_type;
1475 huff_counts->min_space=0;
1476 huff_counts->length_bits=max_bit(max_space_length);
1477 break;
1478 default:
1479 huff_counts->field_type=field_type;
1480 huff_counts->min_space=(uint) min_pos;
1481 huff_counts->pack_type|=PACK_TYPE_SELECTED;
1482 huff_counts->length_bits=max_bit(max_space_length);
1483 break;
1484 }
1485 return(1); /* Using space-compress */
1486 }
1487
1488
1489 /* Make a huff_tree of each huff_count */
1490
make_huff_trees(HUFF_COUNTS * huff_counts,uint trees)1491 static HUFF_TREE* make_huff_trees(HUFF_COUNTS *huff_counts, uint trees)
1492 {
1493 uint tree;
1494 HUFF_TREE *huff_tree;
1495 DBUG_ENTER("make_huff_trees");
1496
1497 if (!(huff_tree=(HUFF_TREE*) my_malloc(PSI_NOT_INSTRUMENTED,
1498 trees*sizeof(HUFF_TREE),
1499 MYF(MY_WME | MY_ZEROFILL))))
1500 DBUG_RETURN(0);
1501
1502 for (tree=0 ; tree < trees ; tree++)
1503 {
1504 if (make_huff_tree(huff_tree+tree,huff_counts+tree))
1505 {
1506 while (tree--)
1507 my_free(huff_tree[tree].element_buffer);
1508 my_free(huff_tree);
1509 DBUG_RETURN(0);
1510 }
1511 }
1512 DBUG_RETURN(huff_tree);
1513 }
1514
1515 /*
1516 Build a Huffman tree.
1517
1518 SYNOPSIS
1519 make_huff_tree()
1520 huff_tree The Huffman tree.
1521 huff_counts The counts.
1522
1523 DESCRIPTION
1524 Build a Huffman tree according to huff_counts->counts or
1525 huff_counts->tree_buff. tree_buff, if non-NULL contains up to
1526 tree_buff_length of distinct column values. In that case, whole
1527 values can be Huffman encoded instead of single bytes.
1528
1529 RETURN
1530 0 OK
1531 != 0 Error
1532 */
1533
make_huff_tree(HUFF_TREE * huff_tree,HUFF_COUNTS * huff_counts)1534 static int make_huff_tree(HUFF_TREE *huff_tree, HUFF_COUNTS *huff_counts)
1535 {
1536 uint i,found,bits_packed,first,last;
1537 my_off_t bytes_packed;
1538 HUFF_ELEMENT *a,*b,*new_huff_el;
1539
1540 first=last=0;
1541 if (huff_counts->tree_buff)
1542 {
1543 /* Calculate the number of distinct values in tree_buff. */
1544 found= (uint) (huff_counts->tree_pos - huff_counts->tree_buff) /
1545 huff_counts->field_length;
1546 first=0; last=found-1;
1547 }
1548 else
1549 {
1550 /* Count the number of byte codes found in the column. */
1551 for (i=found=0 ; i < 256 ; i++)
1552 {
1553 if (huff_counts->counts[i])
1554 {
1555 if (! found++)
1556 first=i;
1557 last=i;
1558 }
1559 }
1560 if (found < 2)
1561 found=2;
1562 }
1563
1564 /* When using 'tree_buff' we can have more that 256 values. */
1565 if (queue.max_elements < found)
1566 {
1567 delete_queue(&queue);
1568 if (init_queue(&queue,found,0,0,compare_huff_elements,0))
1569 return -1;
1570 }
1571
1572 /* Allocate or reallocate an element buffer for the Huffman tree. */
1573 if (!huff_tree->element_buffer)
1574 {
1575 if (!(huff_tree->element_buffer=
1576 (HUFF_ELEMENT*) my_malloc(PSI_NOT_INSTRUMENTED,
1577 found*2*sizeof(HUFF_ELEMENT),MYF(MY_WME))))
1578 return 1;
1579 }
1580 else
1581 {
1582 HUFF_ELEMENT *temp;
1583 if (!(temp=
1584 (HUFF_ELEMENT*) my_realloc(PSI_NOT_INSTRUMENTED,
1585 (uchar*) huff_tree->element_buffer,
1586 found*2*sizeof(HUFF_ELEMENT),
1587 MYF(MY_WME))))
1588 return 1;
1589 huff_tree->element_buffer=temp;
1590 }
1591
1592 huff_counts->tree=huff_tree;
1593 huff_tree->counts=huff_counts;
1594 huff_tree->min_chr=first;
1595 huff_tree->max_chr=last;
1596 huff_tree->char_bits=max_bit(last-first);
1597 huff_tree->offset_bits=max_bit(found-1)+1;
1598
1599 if (huff_counts->tree_buff)
1600 {
1601 huff_tree->elements=0;
1602 huff_tree->tree_pack_length=(1+15+16+5+5+
1603 (huff_tree->char_bits+1)*found+
1604 (huff_tree->offset_bits+1)*
1605 (found-2)+7)/8 +
1606 (uint) (huff_tree->counts->tree_pos-
1607 huff_tree->counts->tree_buff);
1608 /*
1609 Put a HUFF_ELEMENT into the queue for every distinct column value.
1610
1611 tree_walk() calls save_counts_in_queue() for every element in
1612 'int_tree'. This takes elements from the target trees element
1613 buffer and places references to them into the buffer of the
1614 priority queue. We insert in column value order, but the order is
1615 in fact irrelevant here. We will establish the correct order
1616 later.
1617 */
1618 tree_walk(&huff_counts->int_tree,
1619 (int (*)(void*, element_count,void*)) save_counts_in_queue,
1620 (uchar*) huff_tree, left_root_right);
1621 }
1622 else
1623 {
1624 huff_tree->elements=found;
1625 huff_tree->tree_pack_length=(9+9+5+5+
1626 (huff_tree->char_bits+1)*found+
1627 (huff_tree->offset_bits+1)*
1628 (found-2)+7)/8;
1629 /*
1630 Put a HUFF_ELEMENT into the queue for every byte code found in the column.
1631
1632 The elements are taken from the target trees element buffer.
1633 Instead of using queue_insert(), we just place references to the
1634 elements into the buffer of the priority queue. We insert in byte
1635 value order, but the order is in fact irrelevant here. We will
1636 establish the correct order later.
1637 */
1638 for (i=first, found=0 ; i <= last ; i++)
1639 {
1640 if (huff_counts->counts[i])
1641 {
1642 new_huff_el=huff_tree->element_buffer+(found++);
1643 new_huff_el->count=huff_counts->counts[i];
1644 new_huff_el->a.leaf.null=0;
1645 new_huff_el->a.leaf.element_nr=i;
1646 queue.root[found]=(uchar*) new_huff_el;
1647 }
1648 }
1649 /*
1650 If there is only a single byte value in this field in all records,
1651 add a second element with zero incidence. This is required to enter
1652 the loop, which builds the Huffman tree.
1653 */
1654 while (found < 2)
1655 {
1656 new_huff_el=huff_tree->element_buffer+(found++);
1657 new_huff_el->count=0;
1658 new_huff_el->a.leaf.null=0;
1659 if (last)
1660 new_huff_el->a.leaf.element_nr=huff_tree->min_chr=last-1;
1661 else
1662 new_huff_el->a.leaf.element_nr=huff_tree->max_chr=last+1;
1663 queue.root[found]=(uchar*) new_huff_el;
1664 }
1665 }
1666
1667 /* Make a queue from the queue buffer. */
1668 queue.elements=found;
1669
1670 /*
1671 Make a priority queue from the queue. Construct its index so that we
1672 have a partially ordered tree.
1673 */
1674 for (i=found/2 ; i > 0 ; i--)
1675 _downheap(&queue,i);
1676
1677 /* The Huffman algorithm. */
1678 bytes_packed=0; bits_packed=0;
1679 for (i=1 ; i < found ; i++)
1680 {
1681 /*
1682 Pop the top element from the queue (the one with the least incidence).
1683 Popping from a priority queue includes a re-ordering of the queue,
1684 to get the next least incidence element to the top.
1685 */
1686 a=(HUFF_ELEMENT*) queue_remove(&queue,0);
1687 /*
1688 Copy the next least incidence element. The queue implementation
1689 reserves root[0] for temporary purposes. root[1] is the top.
1690 */
1691 b=(HUFF_ELEMENT*) queue.root[1];
1692 /* Get a new element from the element buffer. */
1693 new_huff_el=huff_tree->element_buffer+found+i;
1694 /* The new element gets the sum of the two least incidence elements. */
1695 new_huff_el->count=a->count+b->count;
1696 /*
1697 The Huffman algorithm assigns another bit to the code for a byte
1698 every time that bytes incidence is combined (directly or indirectly)
1699 to a new element as one of the two least incidence elements.
1700 This means that one more bit per incidence of that byte is required
1701 in the resulting file. So we add the new combined incidence as the
1702 number of bits by which the result grows.
1703 */
1704 bits_packed+=(uint) (new_huff_el->count & 7);
1705 bytes_packed+=new_huff_el->count/8;
1706 /* The new element points to its children, lesser in left. */
1707 new_huff_el->a.nod.left=a;
1708 new_huff_el->a.nod.right=b;
1709 /*
1710 Replace the copied top element by the new element and re-order the
1711 queue.
1712 */
1713 queue.root[1]=(uchar*) new_huff_el;
1714 queue_replaced(&queue);
1715 }
1716 huff_tree->root=(HUFF_ELEMENT*) queue.root[1];
1717 huff_tree->bytes_packed=bytes_packed+(bits_packed+7)/8;
1718 return 0;
1719 }
1720
compare_tree(void * cmp_arg MY_ATTRIBUTE ((unused)),const uchar * s,const uchar * t)1721 static int compare_tree(void* cmp_arg MY_ATTRIBUTE((unused)),
1722 const uchar *s, const uchar *t)
1723 {
1724 uint length;
1725 for (length=global_count->field_length; length-- ;)
1726 if (*s++ != *t++)
1727 return (int) s[-1] - (int) t[-1];
1728 return 0;
1729 }
1730
1731 /*
1732 Organize distinct column values and their incidences into a priority queue.
1733
1734 SYNOPSIS
1735 save_counts_in_queue()
1736 key The column value.
1737 count The incidence of this value.
1738 tree The Huffman tree to be built later.
1739
1740 DESCRIPTION
1741 We use the element buffer of the targeted tree. The distinct column
1742 values are organized in a priority queue first. The Huffman
1743 algorithm will later organize the elements into a Huffman tree. For
1744 the time being, we just place references to the elements into the
1745 queue buffer. The buffer will later be organized into a priority
1746 queue.
1747
1748 RETURN
1749 0
1750 */
1751
save_counts_in_queue(uchar * key,element_count count,HUFF_TREE * tree)1752 static int save_counts_in_queue(uchar *key, element_count count,
1753 HUFF_TREE *tree)
1754 {
1755 HUFF_ELEMENT *new_huff_el;
1756
1757 new_huff_el=tree->element_buffer+(tree->elements++);
1758 new_huff_el->count=count;
1759 new_huff_el->a.leaf.null=0;
1760 new_huff_el->a.leaf.element_nr= (uint) (key- tree->counts->tree_buff) /
1761 tree->counts->field_length;
1762 queue.root[tree->elements]=(uchar*) new_huff_el;
1763 return 0;
1764 }
1765
1766
1767 /*
1768 Calculate length of file if given counts should be used.
1769
1770 SYNOPSIS
1771 calc_packed_length()
1772 huff_counts The counts for a column of the table(s).
1773 add_tree_lenght If the decode tree length should be added.
1774
1775 DESCRIPTION
1776 We need to follow the Huffman algorithm until we know, how many bits
1777 are required for each byte code. But we do not need the resulting
1778 Huffman tree. Hence, we can leave out some steps which are essential
1779 in make_huff_tree().
1780
1781 RETURN
1782 Number of bytes required to compress this table column.
1783 */
1784
calc_packed_length(HUFF_COUNTS * huff_counts,uint add_tree_lenght)1785 static my_off_t calc_packed_length(HUFF_COUNTS *huff_counts,
1786 uint add_tree_lenght)
1787 {
1788 uint i,found,bits_packed,first,last;
1789 my_off_t bytes_packed;
1790 HUFF_ELEMENT element_buffer[256];
1791 DBUG_ENTER("calc_packed_length");
1792
1793 /*
1794 WARNING: We use a small hack for efficiency: Instead of placing
1795 references to HUFF_ELEMENTs into the queue, we just insert
1796 references to the counts of the byte codes which appeared in this
1797 table column. During the Huffman algorithm they are successively
1798 replaced by references to HUFF_ELEMENTs. This works, because
1799 HUFF_ELEMENTs have the incidence count at their beginning.
1800 Regardless, wether the queue array contains references to counts of
1801 type my_off_t or references to HUFF_ELEMENTs which have the count of
1802 type my_off_t at their beginning, it always points to a count of the
1803 same type.
1804
1805 Instead of using queue_insert(), we just copy the references into
1806 the buffer of the priority queue. We insert in byte value order, but
1807 the order is in fact irrelevant here. We will establish the correct
1808 order later.
1809 */
1810 first=last=0;
1811 for (i=found=0 ; i < 256 ; i++)
1812 {
1813 if (huff_counts->counts[i])
1814 {
1815 if (! found++)
1816 first=i;
1817 last=i;
1818 /* We start with root[1], which is the queues top element. */
1819 queue.root[found]=(uchar*) &huff_counts->counts[i];
1820 }
1821 }
1822 if (!found)
1823 DBUG_RETURN(0); /* Empty tree */
1824 /*
1825 If there is only a single byte value in this field in all records,
1826 add a second element with zero incidence. This is required to enter
1827 the loop, which follows the Huffman algorithm.
1828 */
1829 if (found < 2)
1830 queue.root[++found]=(uchar*) &huff_counts->counts[last ? 0 : 1];
1831
1832 /* Make a queue from the queue buffer. */
1833 queue.elements=found;
1834
1835 bytes_packed=0; bits_packed=0;
1836 /* Add the length of the coding table, which would become part of the file. */
1837 if (add_tree_lenght)
1838 bytes_packed=(8+9+5+5+(max_bit(last-first)+1)*found+
1839 (max_bit(found-1)+1+1)*(found-2) +7)/8;
1840
1841 /*
1842 Make a priority queue from the queue. Construct its index so that we
1843 have a partially ordered tree.
1844 */
1845 for (i=(found+1)/2 ; i > 0 ; i--)
1846 _downheap(&queue,i);
1847
1848 /* The Huffman algorithm. */
1849 for (i=0 ; i < found-1 ; i++)
1850 {
1851 my_off_t *a;
1852 my_off_t *b;
1853 HUFF_ELEMENT *new_huff_el;
1854
1855 /*
1856 Pop the top element from the queue (the one with the least
1857 incidence). Popping from a priority queue includes a re-ordering
1858 of the queue, to get the next least incidence element to the top.
1859 */
1860 a= (my_off_t*) queue_remove(&queue, 0);
1861 /*
1862 Copy the next least incidence element. The queue implementation
1863 reserves root[0] for temporary purposes. root[1] is the top.
1864 */
1865 b= (my_off_t*) queue.root[1];
1866 /* Create a new element in a local (automatic) buffer. */
1867 new_huff_el= element_buffer + i;
1868 /* The new element gets the sum of the two least incidence elements. */
1869 new_huff_el->count= *a + *b;
1870 /*
1871 The Huffman algorithm assigns another bit to the code for a byte
1872 every time that bytes incidence is combined (directly or indirectly)
1873 to a new element as one of the two least incidence elements.
1874 This means that one more bit per incidence of that byte is required
1875 in the resulting file. So we add the new combined incidence as the
1876 number of bits by which the result grows.
1877 */
1878 bits_packed+=(uint) (new_huff_el->count & 7);
1879 bytes_packed+=new_huff_el->count/8;
1880 /*
1881 Replace the copied top element by the new element and re-order the
1882 queue. This successively replaces the references to counts by
1883 references to HUFF_ELEMENTs.
1884 */
1885 queue.root[1]=(uchar*) new_huff_el;
1886 queue_replaced(&queue);
1887 }
1888 DBUG_RETURN(bytes_packed+(bits_packed+7)/8);
1889 }
1890
1891
1892 /* Remove trees that don't give any compression */
1893
join_same_trees(HUFF_COUNTS * huff_counts,uint trees)1894 static uint join_same_trees(HUFF_COUNTS *huff_counts, uint trees)
1895 {
1896 uint k,tree_number;
1897 HUFF_COUNTS count,*i,*j,*last_count;
1898
1899 last_count=huff_counts+trees;
1900 for (tree_number=0, i=huff_counts ; i < last_count ; i++)
1901 {
1902 if (!i->tree->tree_number)
1903 {
1904 i->tree->tree_number= ++tree_number;
1905 if (i->tree_buff)
1906 continue; /* Don't join intervall */
1907 for (j=i+1 ; j < last_count ; j++)
1908 {
1909 if (! j->tree->tree_number && ! j->tree_buff)
1910 {
1911 for (k=0 ; k < 256 ; k++)
1912 count.counts[k]=i->counts[k]+j->counts[k];
1913 if (calc_packed_length(&count,1) <=
1914 i->tree->bytes_packed + j->tree->bytes_packed+
1915 i->tree->tree_pack_length+j->tree->tree_pack_length+
1916 ALLOWED_JOIN_DIFF)
1917 {
1918 memcpy(i->counts, count.counts,
1919 sizeof(count.counts[0])*256);
1920 my_free(j->tree->element_buffer);
1921 j->tree->element_buffer=0;
1922 j->tree=i->tree;
1923 memmove((uchar*) i->counts, (uchar*) count.counts,
1924 sizeof(count.counts[0]) * 256);
1925 if (make_huff_tree(i->tree,i))
1926 return (uint) -1;
1927 }
1928 }
1929 }
1930 }
1931 }
1932 DBUG_PRINT("info", ("Original trees: %d After join: %d",
1933 trees, tree_number));
1934 if (verbose)
1935 printf("Original trees: %d After join: %d\n", trees, tree_number);
1936 return tree_number; /* Return trees left */
1937 }
1938
1939
1940 /*
1941 Fill in huff_tree encode tables.
1942
1943 SYNOPSIS
1944 make_huff_decode_table()
1945 huff_tree An array of HUFF_TREE which are to be encoded.
1946 trees The number of HUFF_TREE in the array.
1947
1948 RETURN
1949 0 success
1950 != 0 error
1951 */
1952
make_huff_decode_table(HUFF_TREE * huff_tree,uint trees)1953 static int make_huff_decode_table(HUFF_TREE *huff_tree, uint trees)
1954 {
1955 uint elements;
1956 for ( ; trees-- ; huff_tree++)
1957 {
1958 if (huff_tree->tree_number > 0)
1959 {
1960 elements=huff_tree->counts->tree_buff ? huff_tree->elements : 256;
1961 if (!(huff_tree->code =
1962 (ulonglong*) my_malloc(PSI_NOT_INSTRUMENTED,
1963 elements*
1964 (sizeof(ulonglong) + sizeof(uchar)),
1965 MYF(MY_WME | MY_ZEROFILL))))
1966 return 1;
1967 huff_tree->code_len=(uchar*) (huff_tree->code+elements);
1968 make_traverse_code_tree(huff_tree, huff_tree->root,
1969 8 * sizeof(ulonglong), 0LL);
1970 }
1971 }
1972 return 0;
1973 }
1974
1975
make_traverse_code_tree(HUFF_TREE * huff_tree,HUFF_ELEMENT * element,uint size,ulonglong code)1976 static void make_traverse_code_tree(HUFF_TREE *huff_tree,
1977 HUFF_ELEMENT *element,
1978 uint size, ulonglong code)
1979 {
1980 uint chr;
1981 if (!element->a.leaf.null)
1982 {
1983 chr=element->a.leaf.element_nr;
1984 huff_tree->code_len[chr]= (uchar) (8 * sizeof(ulonglong) - size);
1985 huff_tree->code[chr]= (code >> size);
1986 if (huff_tree->height < 8 * sizeof(ulonglong) - size)
1987 huff_tree->height= 8 * sizeof(ulonglong) - size;
1988 }
1989 else
1990 {
1991 size--;
1992 make_traverse_code_tree(huff_tree,element->a.nod.left,size,code);
1993 make_traverse_code_tree(huff_tree, element->a.nod.right, size,
1994 code + (((ulonglong) 1) << size));
1995 }
1996 return;
1997 }
1998
1999
2000 /*
2001 Convert a value into binary digits.
2002
2003 SYNOPSIS
2004 bindigits()
2005 value The value.
2006 length The number of low order bits to convert.
2007
2008 NOTE
2009 The result string is in static storage. It is reused on every call.
2010 So you cannot use it twice in one expression.
2011
2012 RETURN
2013 A pointer to a static NUL-terminated string.
2014 */
2015
bindigits(ulonglong value,uint bits)2016 static char *bindigits(ulonglong value, uint bits)
2017 {
2018 static char digits[72];
2019 char *ptr= digits;
2020 uint idx= bits;
2021
2022 assert(idx < sizeof(digits));
2023 while (idx)
2024 *(ptr++)= '0' + ((char) (value >> (--idx)) & (char) 1);
2025 *ptr= '\0';
2026 return digits;
2027 }
2028
2029
2030 /*
2031 Convert a value into hexadecimal digits.
2032
2033 SYNOPSIS
2034 hexdigits()
2035 value The value.
2036
2037 NOTE
2038 The result string is in static storage. It is reused on every call.
2039 So you cannot use it twice in one expression.
2040
2041 RETURN
2042 A pointer to a static NUL-terminated string.
2043 */
2044
hexdigits(ulonglong value)2045 static char *hexdigits(ulonglong value)
2046 {
2047 static char digits[20];
2048 char *ptr= digits;
2049 uint idx= 2 * sizeof(value); /* Two hex digits per byte. */
2050
2051 assert(idx < sizeof(digits));
2052 while (idx)
2053 {
2054 if ((*(ptr++)= '0' + ((char) (value >> (4 * (--idx))) & (char) 0xf)) > '9')
2055 *(ptr - 1)+= 'a' - '9' - 1;
2056 }
2057 *ptr= '\0';
2058 return digits;
2059 }
2060
2061
2062 /* Write header to new packed data file */
2063
write_header(PACK_MRG_INFO * mrg,uint head_length,uint trees,my_off_t tot_elements,my_off_t filelength)2064 static int write_header(PACK_MRG_INFO *mrg,uint head_length,uint trees,
2065 my_off_t tot_elements,my_off_t filelength)
2066 {
2067 uchar *buff= (uchar*) file_buffer.pos;
2068
2069 memset(buff, 0, HEAD_LENGTH);
2070 memcpy(buff,myisam_pack_file_magic,4);
2071 int4store(buff+4,head_length);
2072 int4store(buff+8, mrg->min_pack_length);
2073 int4store(buff+12,mrg->max_pack_length);
2074 int4store(buff+16, (uint32)tot_elements);
2075 int4store(buff+20, (uint32)intervall_length);
2076 int2store(buff+24,trees);
2077 buff[26]=(char) mrg->ref_length;
2078 /* Save record pointer length */
2079 buff[27]= (uchar) mi_get_pointer_length((ulonglong) filelength,2);
2080 if (test_only)
2081 return 0;
2082 my_seek(file_buffer.file,0L,MY_SEEK_SET,MYF(0));
2083 return my_write(file_buffer.file,(const uchar *) file_buffer.pos,HEAD_LENGTH,
2084 MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)) != 0;
2085 }
2086
2087 /* Write fieldinfo to new packed file */
2088
write_field_info(HUFF_COUNTS * counts,uint fields,uint trees)2089 static void write_field_info(HUFF_COUNTS *counts, uint fields, uint trees)
2090 {
2091 uint i;
2092 uint huff_tree_bits;
2093 huff_tree_bits=max_bit(trees ? trees-1 : 0);
2094
2095 DBUG_PRINT("info", (" "));
2096 DBUG_PRINT("info", ("column types:"));
2097 DBUG_PRINT("info", ("FIELD_NORMAL 0"));
2098 DBUG_PRINT("info", ("FIELD_SKIP_ENDSPACE 1"));
2099 DBUG_PRINT("info", ("FIELD_SKIP_PRESPACE 2"));
2100 DBUG_PRINT("info", ("FIELD_SKIP_ZERO 3"));
2101 DBUG_PRINT("info", ("FIELD_BLOB 4"));
2102 DBUG_PRINT("info", ("FIELD_CONSTANT 5"));
2103 DBUG_PRINT("info", ("FIELD_INTERVALL 6"));
2104 DBUG_PRINT("info", ("FIELD_ZERO 7"));
2105 DBUG_PRINT("info", ("FIELD_VARCHAR 8"));
2106 DBUG_PRINT("info", ("FIELD_CHECK 9"));
2107 DBUG_PRINT("info", (" "));
2108 DBUG_PRINT("info", ("pack type as a set of flags:"));
2109 DBUG_PRINT("info", ("PACK_TYPE_SELECTED 1"));
2110 DBUG_PRINT("info", ("PACK_TYPE_SPACE_FIELDS 2"));
2111 DBUG_PRINT("info", ("PACK_TYPE_ZERO_FILL 4"));
2112 DBUG_PRINT("info", (" "));
2113 if (verbose >= 2)
2114 {
2115 printf("\n");
2116 printf("column types:\n");
2117 printf("FIELD_NORMAL 0\n");
2118 printf("FIELD_SKIP_ENDSPACE 1\n");
2119 printf("FIELD_SKIP_PRESPACE 2\n");
2120 printf("FIELD_SKIP_ZERO 3\n");
2121 printf("FIELD_BLOB 4\n");
2122 printf("FIELD_CONSTANT 5\n");
2123 printf("FIELD_INTERVALL 6\n");
2124 printf("FIELD_ZERO 7\n");
2125 printf("FIELD_VARCHAR 8\n");
2126 printf("FIELD_CHECK 9\n");
2127 printf("\n");
2128 printf("pack type as a set of flags:\n");
2129 printf("PACK_TYPE_SELECTED 1\n");
2130 printf("PACK_TYPE_SPACE_FIELDS 2\n");
2131 printf("PACK_TYPE_ZERO_FILL 4\n");
2132 printf("\n");
2133 }
2134 for (i=0 ; i++ < fields ; counts++)
2135 {
2136 write_bits((ulonglong) (int) counts->field_type, 5);
2137 write_bits(counts->pack_type,6);
2138 if (counts->pack_type & PACK_TYPE_ZERO_FILL)
2139 write_bits(counts->max_zero_fill,5);
2140 else
2141 write_bits(counts->length_bits,5);
2142 write_bits((ulonglong) counts->tree->tree_number - 1, huff_tree_bits);
2143 DBUG_PRINT("info", ("column: %3u type: %2u pack: %2u zero: %4u "
2144 "lbits: %2u tree: %2u length: %4u",
2145 i , counts->field_type, counts->pack_type,
2146 counts->max_zero_fill, counts->length_bits,
2147 counts->tree->tree_number, counts->field_length));
2148 if (verbose >= 2)
2149 printf("column: %3u type: %2u pack: %2u zero: %4u lbits: %2u "
2150 "tree: %2u length: %4u\n", i , counts->field_type,
2151 counts->pack_type, counts->max_zero_fill, counts->length_bits,
2152 counts->tree->tree_number, counts->field_length);
2153 }
2154 flush_bits();
2155 return;
2156 }
2157
2158 /* Write all huff_trees to new datafile. Return tot count of
2159 elements in all trees
2160 Returns 0 on error */
2161
write_huff_tree(HUFF_TREE * huff_tree,uint trees)2162 static my_off_t write_huff_tree(HUFF_TREE *huff_tree, uint trees)
2163 {
2164 uint i,int_length;
2165 uint tree_no;
2166 uint codes;
2167 uint errors= 0;
2168 uint *packed_tree,*offset,length;
2169 my_off_t elements;
2170
2171 /* Find the highest number of elements in the trees. */
2172 for (i=length=0 ; i < trees ; i++)
2173 if (huff_tree[i].tree_number > 0 && huff_tree[i].elements > length)
2174 length=huff_tree[i].elements;
2175 /*
2176 Allocate a buffer for packing a decode tree. Two numbers per element
2177 (left child and right child).
2178 */
2179 if (!(packed_tree=(uint*) my_alloca(sizeof(uint)*length*2)))
2180 {
2181 my_error(EE_OUTOFMEMORY, MYF(ME_FATALERROR),
2182 sizeof(uint)*length*2);
2183 return 0;
2184 }
2185
2186 DBUG_PRINT("info", (" "));
2187 if (verbose >= 2)
2188 printf("\n");
2189 tree_no= 0;
2190 intervall_length=0;
2191 for (elements=0; trees-- ; huff_tree++)
2192 {
2193 /* Skip columns that have been joined with other columns. */
2194 if (huff_tree->tree_number == 0)
2195 continue; /* Deleted tree */
2196 tree_no++;
2197 DBUG_PRINT("info", (" "));
2198 if (verbose >= 3)
2199 printf("\n");
2200 /* Count the total number of elements (byte codes or column values). */
2201 elements+=huff_tree->elements;
2202 huff_tree->max_offset=2;
2203 /* Build a tree of offsets and codes for decoding in 'packed_tree'. */
2204 if (huff_tree->elements <= 1)
2205 offset=packed_tree;
2206 else
2207 offset=make_offset_code_tree(huff_tree,huff_tree->root,packed_tree);
2208
2209 /* This should be the same as 'length' above. */
2210 huff_tree->offset_bits=max_bit(huff_tree->max_offset);
2211
2212 /*
2213 Since we check this during collecting the distinct column values,
2214 this should never happen.
2215 */
2216 if (huff_tree->max_offset >= IS_OFFSET)
2217 { /* This should be impossible */
2218 (void) fprintf(stderr, "Tree offset got too big: %d, aborted\n",
2219 huff_tree->max_offset);
2220 return 0;
2221 }
2222
2223 DBUG_PRINT("info", ("pos: %lu elements: %u tree-elements: %lu "
2224 "char_bits: %u\n",
2225 (ulong) (file_buffer.pos - file_buffer.buffer),
2226 huff_tree->elements, (ulong) (offset - packed_tree),
2227 huff_tree->char_bits));
2228 if (!huff_tree->counts->tree_buff)
2229 {
2230 /* We do a byte compression on this column. Mark with bit 0. */
2231 write_bits(0,1);
2232 write_bits(huff_tree->min_chr,8);
2233 write_bits(huff_tree->elements,9);
2234 write_bits(huff_tree->char_bits,5);
2235 write_bits(huff_tree->offset_bits,5);
2236 int_length=0;
2237 }
2238 else
2239 {
2240 int_length=(uint) (huff_tree->counts->tree_pos -
2241 huff_tree->counts->tree_buff);
2242 /* We have distinct column values for this column. Mark with bit 1. */
2243 write_bits(1,1);
2244 write_bits(huff_tree->elements,15);
2245 write_bits(int_length,16);
2246 write_bits(huff_tree->char_bits,5);
2247 write_bits(huff_tree->offset_bits,5);
2248 intervall_length+=int_length;
2249 }
2250 DBUG_PRINT("info", ("tree: %2u elements: %4u char_bits: %2u "
2251 "offset_bits: %2u %s: %5u codelen: %2u",
2252 tree_no, huff_tree->elements, huff_tree->char_bits,
2253 huff_tree->offset_bits, huff_tree->counts->tree_buff ?
2254 "bufflen" : "min_chr", huff_tree->counts->tree_buff ?
2255 int_length : huff_tree->min_chr, huff_tree->height));
2256 if (verbose >= 2)
2257 printf("tree: %2u elements: %4u char_bits: %2u offset_bits: %2u "
2258 "%s: %5u codelen: %2u\n", tree_no, huff_tree->elements,
2259 huff_tree->char_bits, huff_tree->offset_bits,
2260 huff_tree->counts->tree_buff ? "bufflen" : "min_chr",
2261 huff_tree->counts->tree_buff ? int_length :
2262 huff_tree->min_chr, huff_tree->height);
2263
2264 /* Check that the code tree length matches the element count. */
2265 length=(uint) (offset-packed_tree);
2266 if (length != huff_tree->elements*2-2)
2267 {
2268 (void) fprintf(stderr, "error: Huff-tree-length: %d != calc_length: %d\n",
2269 length, huff_tree->elements * 2 - 2);
2270 errors++;
2271 break;
2272 }
2273
2274 for (i=0 ; i < length ; i++)
2275 {
2276 if (packed_tree[i] & IS_OFFSET)
2277 write_bits(packed_tree[i] - IS_OFFSET+ (1 << huff_tree->offset_bits),
2278 huff_tree->offset_bits+1);
2279 else
2280 write_bits(packed_tree[i]-huff_tree->min_chr,huff_tree->char_bits+1);
2281 DBUG_PRINT("info", ("tree[0x%04x]: %s0x%04x",
2282 i, (packed_tree[i] & IS_OFFSET) ?
2283 " -> " : "", (packed_tree[i] & IS_OFFSET) ?
2284 packed_tree[i] - IS_OFFSET + i : packed_tree[i]));
2285 if (verbose >= 3)
2286 printf("tree[0x%04x]: %s0x%04x\n",
2287 i, (packed_tree[i] & IS_OFFSET) ? " -> " : "",
2288 (packed_tree[i] & IS_OFFSET) ?
2289 packed_tree[i] - IS_OFFSET + i : packed_tree[i]);
2290 }
2291 flush_bits();
2292
2293 /*
2294 Display coding tables and check their correctness.
2295 */
2296 codes= huff_tree->counts->tree_buff ? huff_tree->elements : 256;
2297 for (i= 0; i < codes; i++)
2298 {
2299 ulonglong code;
2300 uint bits;
2301 uint len;
2302 uint idx;
2303
2304 if (! (len= huff_tree->code_len[i]))
2305 continue;
2306 DBUG_PRINT("info", ("code[0x%04x]: 0x%s bits: %2u bin: %s", i,
2307 hexdigits(huff_tree->code[i]), huff_tree->code_len[i],
2308 bindigits(huff_tree->code[i],
2309 huff_tree->code_len[i])));
2310 if (verbose >= 3)
2311 printf("code[0x%04x]: 0x%s bits: %2u bin: %s\n", i,
2312 hexdigits(huff_tree->code[i]), huff_tree->code_len[i],
2313 bindigits(huff_tree->code[i], huff_tree->code_len[i]));
2314
2315 /* Check that the encode table decodes correctly. */
2316 code= 0;
2317 bits= 0;
2318 idx= 0;
2319 DBUG_EXECUTE_IF("forcechkerr1", len--;);
2320 DBUG_EXECUTE_IF("forcechkerr2", bits= 8 * sizeof(code););
2321 DBUG_EXECUTE_IF("forcechkerr3", idx= length;);
2322 for (;;)
2323 {
2324 if (! len)
2325 {
2326 (void) fflush(stdout);
2327 (void) fprintf(stderr, "error: code 0x%s with %u bits not found\n",
2328 hexdigits(huff_tree->code[i]), huff_tree->code_len[i]);
2329 errors++;
2330 break;
2331 }
2332 code<<= 1;
2333 code|= (huff_tree->code[i] >> (--len)) & 1;
2334 bits++;
2335 if (bits > 8 * sizeof(code))
2336 {
2337 (void) fflush(stdout);
2338 (void) fprintf(stderr, "error: Huffman code too long: %u/%u\n",
2339 bits, (uint) (8 * sizeof(code)));
2340 errors++;
2341 break;
2342 }
2343 idx+= (uint) code & 1;
2344 if (idx >= length)
2345 {
2346 (void) fflush(stdout);
2347 (void) fprintf(stderr, "error: illegal tree offset: %u/%u\n",
2348 idx, length);
2349 errors++;
2350 break;
2351 }
2352 if (packed_tree[idx] & IS_OFFSET)
2353 idx+= packed_tree[idx] & ~IS_OFFSET;
2354 else
2355 break; /* Hit a leaf. This contains the result value. */
2356 }
2357 if (errors)
2358 break;
2359
2360 DBUG_EXECUTE_IF("forcechkerr4", packed_tree[idx]++;);
2361 if (packed_tree[idx] != i)
2362 {
2363 (void) fflush(stdout);
2364 (void) fprintf(stderr, "error: decoded value 0x%04x should be: 0x%04x\n",
2365 packed_tree[idx], i);
2366 errors++;
2367 break;
2368 }
2369 } /*end for (codes)*/
2370 if (errors)
2371 break;
2372
2373 /* Write column values in case of distinct column value compression. */
2374 if (huff_tree->counts->tree_buff)
2375 {
2376 for (i=0 ; i < int_length ; i++)
2377 {
2378 write_bits((ulonglong) (uchar) huff_tree->counts->tree_buff[i], 8);
2379 DBUG_PRINT("info", ("column_values[0x%04x]: 0x%02x",
2380 i, (uchar) huff_tree->counts->tree_buff[i]));
2381 if (verbose >= 3)
2382 printf("column_values[0x%04x]: 0x%02x\n",
2383 i, (uchar) huff_tree->counts->tree_buff[i]);
2384 }
2385 }
2386 flush_bits();
2387 }
2388 DBUG_PRINT("info", (" "));
2389 if (verbose >= 2)
2390 printf("\n");
2391 if (errors)
2392 {
2393 (void) fprintf(stderr, "Error: Generated decode trees are corrupt. Stop.\n");
2394 return 0;
2395 }
2396 return elements;
2397 }
2398
2399
make_offset_code_tree(HUFF_TREE * huff_tree,HUFF_ELEMENT * element,uint * offset)2400 static uint *make_offset_code_tree(HUFF_TREE *huff_tree, HUFF_ELEMENT *element,
2401 uint *offset)
2402 {
2403 uint *prev_offset;
2404
2405 prev_offset= offset;
2406 /*
2407 'a.leaf.null' takes the same place as 'a.nod.left'. If this is null,
2408 then there is no left child and, hence no right child either. This
2409 is a property of a binary tree. An element is either a node with two
2410 childs, or a leaf without childs.
2411
2412 The current element is always a node with two childs. Go left first.
2413 */
2414 if (!element->a.nod.left->a.leaf.null)
2415 {
2416 /* Store the byte code or the index of the column value. */
2417 prev_offset[0] =(uint) element->a.nod.left->a.leaf.element_nr;
2418 offset+=2;
2419 }
2420 else
2421 {
2422 /*
2423 Recursively traverse the tree to the left. Mark it as an offset to
2424 another tree node (in contrast to a byte code or column value index).
2425 */
2426 prev_offset[0]= IS_OFFSET+2;
2427 offset=make_offset_code_tree(huff_tree,element->a.nod.left,offset+2);
2428 }
2429
2430 /* Now, check the right child. */
2431 if (!element->a.nod.right->a.leaf.null)
2432 {
2433 /* Store the byte code or the index of the column value. */
2434 prev_offset[1]=element->a.nod.right->a.leaf.element_nr;
2435 return offset;
2436 }
2437 else
2438 {
2439 /*
2440 Recursively traverse the tree to the right. Mark it as an offset to
2441 another tree node (in contrast to a byte code or column value index).
2442 */
2443 uint temp=(uint) (offset-prev_offset-1);
2444 prev_offset[1]= IS_OFFSET+ temp;
2445 if (huff_tree->max_offset < temp)
2446 huff_tree->max_offset = temp;
2447 return make_offset_code_tree(huff_tree,element->a.nod.right,offset);
2448 }
2449 }
2450
2451 /* Get number of bits neaded to represent value */
2452
max_bit(uint value)2453 static uint max_bit(uint value)
2454 {
2455 uint power=1;
2456
2457 while ((value>>=1))
2458 power++;
2459 return (power);
2460 }
2461
2462
compress_isam_file(PACK_MRG_INFO * mrg,HUFF_COUNTS * huff_counts)2463 static int compress_isam_file(PACK_MRG_INFO *mrg, HUFF_COUNTS *huff_counts)
2464 {
2465 int error;
2466 uint i,max_calc_length,pack_ref_length,min_record_length,max_record_length,
2467 intervall,field_length,max_pack_length,pack_blob_length;
2468 my_off_t record_count;
2469 char llbuf[32];
2470 ulong length,pack_length;
2471 uchar *record,*pos,*end_pos,*record_pos,*start_pos;
2472 HUFF_COUNTS *count,*end_count;
2473 HUFF_TREE *tree;
2474 MI_INFO *isam_file=mrg->file[0];
2475 uint pack_version= (uint) isam_file->s->pack.version;
2476 DBUG_ENTER("compress_isam_file");
2477
2478 /* Allocate a buffer for the records (excluding blobs). */
2479 if (!(record=(uchar*) my_alloca(isam_file->s->base.reclength)))
2480 DBUG_RETURN(-1);
2481
2482 end_count=huff_counts+isam_file->s->base.fields;
2483 min_record_length= (uint) ~0;
2484 max_record_length=0;
2485
2486 /*
2487 Calculate the maximum number of bits required to pack the records.
2488 Remember to understand 'max_zero_fill' as 'min_zero_fill'.
2489 The tree height determines the maximum number of bits per value.
2490 Some fields skip leading or trailing spaces or zeroes. The skipped
2491 number of bytes is encoded by 'length_bits' bits.
2492 Empty blobs and varchar are encoded with a single 1 bit. Other blobs
2493 and varchar get a leading 0 bit.
2494 */
2495 for (i=max_calc_length=0 ; i < isam_file->s->base.fields ; i++)
2496 {
2497 if (!(huff_counts[i].pack_type & PACK_TYPE_ZERO_FILL))
2498 huff_counts[i].max_zero_fill=0;
2499 if (huff_counts[i].field_type == FIELD_CONSTANT ||
2500 huff_counts[i].field_type == FIELD_ZERO ||
2501 huff_counts[i].field_type == FIELD_CHECK)
2502 continue;
2503 if (huff_counts[i].field_type == FIELD_INTERVALL)
2504 max_calc_length+=huff_counts[i].tree->height;
2505 else if (huff_counts[i].field_type == FIELD_BLOB ||
2506 huff_counts[i].field_type == FIELD_VARCHAR)
2507 max_calc_length+=huff_counts[i].tree->height*huff_counts[i].max_length + huff_counts[i].length_bits +1;
2508 else
2509 max_calc_length+=
2510 (huff_counts[i].field_length - huff_counts[i].max_zero_fill)*
2511 huff_counts[i].tree->height+huff_counts[i].length_bits;
2512 }
2513 max_calc_length= (max_calc_length + 7) / 8;
2514 pack_ref_length= calc_pack_length(pack_version, max_calc_length);
2515 record_count=0;
2516 /* 'max_blob_length' is the max length of all blobs of a record. */
2517 pack_blob_length= isam_file->s->base.blobs ?
2518 calc_pack_length(pack_version, mrg->max_blob_length) : 0;
2519 max_pack_length=pack_ref_length+pack_blob_length;
2520
2521 DBUG_PRINT("fields", ("==="));
2522 mrg_reset(mrg);
2523 while ((error=mrg_rrnd(mrg,record)) != HA_ERR_END_OF_FILE)
2524 {
2525 ulong tot_blob_length=0;
2526 if (! error)
2527 {
2528 if (flush_buffer((ulong) max_calc_length + (ulong) max_pack_length))
2529 break;
2530 record_pos= (uchar*) file_buffer.pos;
2531 file_buffer.pos+=max_pack_length;
2532 for (start_pos=record, count= huff_counts; count < end_count ; count++)
2533 {
2534 end_pos=start_pos+(field_length=count->field_length);
2535 tree=count->tree;
2536
2537 DBUG_PRINT("fields", ("column: %3lu type: %2u pack: %2u zero: %4u "
2538 "lbits: %2u tree: %2u length: %4u",
2539 (ulong) (count - huff_counts + 1),
2540 count->field_type,
2541 count->pack_type, count->max_zero_fill,
2542 count->length_bits, count->tree->tree_number,
2543 count->field_length));
2544
2545 /* Check if the column contains spaces only. */
2546 if (count->pack_type & PACK_TYPE_SPACE_FIELDS)
2547 {
2548 for (pos=start_pos ; *pos == ' ' && pos < end_pos; pos++) ;
2549 if (pos == end_pos)
2550 {
2551 DBUG_PRINT("fields",
2552 ("PACK_TYPE_SPACE_FIELDS spaces only, bits: 1"));
2553 DBUG_PRINT("fields", ("---"));
2554 write_bits(1,1);
2555 start_pos=end_pos;
2556 continue;
2557 }
2558 DBUG_PRINT("fields",
2559 ("PACK_TYPE_SPACE_FIELDS not only spaces, bits: 1"));
2560 write_bits(0,1);
2561 }
2562 end_pos-=count->max_zero_fill;
2563 field_length-=count->max_zero_fill;
2564
2565 switch (count->field_type) {
2566 case FIELD_SKIP_ZERO:
2567 if (!memcmp((uchar*) start_pos,zero_string,field_length))
2568 {
2569 DBUG_PRINT("fields", ("FIELD_SKIP_ZERO zeroes only, bits: 1"));
2570 write_bits(1,1);
2571 start_pos=end_pos;
2572 break;
2573 }
2574 DBUG_PRINT("fields", ("FIELD_SKIP_ZERO not only zeroes, bits: 1"));
2575 write_bits(0,1);
2576 /* Fall through */
2577 case FIELD_NORMAL:
2578 DBUG_PRINT("fields", ("FIELD_NORMAL %lu bytes",
2579 (ulong) (end_pos - start_pos)));
2580 for ( ; start_pos < end_pos ; start_pos++)
2581 {
2582 DBUG_PRINT("fields",
2583 ("value: 0x%02x code: 0x%s bits: %2u bin: %s",
2584 (uchar) *start_pos,
2585 hexdigits(tree->code[(uchar) *start_pos]),
2586 (uint) tree->code_len[(uchar) *start_pos],
2587 bindigits(tree->code[(uchar) *start_pos],
2588 (uint) tree->code_len[(uchar) *start_pos])));
2589 write_bits(tree->code[(uchar) *start_pos],
2590 (uint) tree->code_len[(uchar) *start_pos]);
2591 }
2592 break;
2593 case FIELD_SKIP_ENDSPACE:
2594 for (pos=end_pos ; pos > start_pos && pos[-1] == ' ' ; pos--) ;
2595 length= (ulong) (end_pos - pos);
2596 if (count->pack_type & PACK_TYPE_SELECTED)
2597 {
2598 if (length > count->min_space)
2599 {
2600 DBUG_PRINT("fields",
2601 ("FIELD_SKIP_ENDSPACE more than min_space, bits: 1"));
2602 DBUG_PRINT("fields",
2603 ("FIELD_SKIP_ENDSPACE skip %lu/%u bytes, bits: %2u",
2604 length, field_length, count->length_bits));
2605 write_bits(1,1);
2606 write_bits(length,count->length_bits);
2607 }
2608 else
2609 {
2610 DBUG_PRINT("fields",
2611 ("FIELD_SKIP_ENDSPACE not more than min_space, "
2612 "bits: 1"));
2613 write_bits(0,1);
2614 pos=end_pos;
2615 }
2616 }
2617 else
2618 {
2619 DBUG_PRINT("fields",
2620 ("FIELD_SKIP_ENDSPACE skip %lu/%u bytes, bits: %2u",
2621 length, field_length, count->length_bits));
2622 write_bits(length,count->length_bits);
2623 }
2624 /* Encode all significant bytes. */
2625 DBUG_PRINT("fields", ("FIELD_SKIP_ENDSPACE %lu bytes",
2626 (ulong) (pos - start_pos)));
2627 for ( ; start_pos < pos ; start_pos++)
2628 {
2629 DBUG_PRINT("fields",
2630 ("value: 0x%02x code: 0x%s bits: %2u bin: %s",
2631 (uchar) *start_pos,
2632 hexdigits(tree->code[(uchar) *start_pos]),
2633 (uint) tree->code_len[(uchar) *start_pos],
2634 bindigits(tree->code[(uchar) *start_pos],
2635 (uint) tree->code_len[(uchar) *start_pos])));
2636 write_bits(tree->code[(uchar) *start_pos],
2637 (uint) tree->code_len[(uchar) *start_pos]);
2638 }
2639 start_pos=end_pos;
2640 break;
2641 case FIELD_SKIP_PRESPACE:
2642 for (pos=start_pos ; pos < end_pos && pos[0] == ' ' ; pos++) ;
2643 length= (ulong) (pos - start_pos);
2644 if (count->pack_type & PACK_TYPE_SELECTED)
2645 {
2646 if (length > count->min_space)
2647 {
2648 DBUG_PRINT("fields",
2649 ("FIELD_SKIP_PRESPACE more than min_space, bits: 1"));
2650 DBUG_PRINT("fields",
2651 ("FIELD_SKIP_PRESPACE skip %lu/%u bytes, bits: %2u",
2652 length, field_length, count->length_bits));
2653 write_bits(1,1);
2654 write_bits(length,count->length_bits);
2655 }
2656 else
2657 {
2658 DBUG_PRINT("fields",
2659 ("FIELD_SKIP_PRESPACE not more than min_space, "
2660 "bits: 1"));
2661 pos=start_pos;
2662 write_bits(0,1);
2663 }
2664 }
2665 else
2666 {
2667 DBUG_PRINT("fields",
2668 ("FIELD_SKIP_PRESPACE skip %lu/%u bytes, bits: %2u",
2669 length, field_length, count->length_bits));
2670 write_bits(length,count->length_bits);
2671 }
2672 /* Encode all significant bytes. */
2673 DBUG_PRINT("fields", ("FIELD_SKIP_PRESPACE %lu bytes",
2674 (ulong) (end_pos - start_pos)));
2675 for (start_pos=pos ; start_pos < end_pos ; start_pos++)
2676 {
2677 DBUG_PRINT("fields",
2678 ("value: 0x%02x code: 0x%s bits: %2u bin: %s",
2679 (uchar) *start_pos,
2680 hexdigits(tree->code[(uchar) *start_pos]),
2681 (uint) tree->code_len[(uchar) *start_pos],
2682 bindigits(tree->code[(uchar) *start_pos],
2683 (uint) tree->code_len[(uchar) *start_pos])));
2684 write_bits(tree->code[(uchar) *start_pos],
2685 (uint) tree->code_len[(uchar) *start_pos]);
2686 }
2687 break;
2688 case FIELD_CONSTANT:
2689 case FIELD_ZERO:
2690 case FIELD_CHECK:
2691 DBUG_PRINT("fields", ("FIELD_CONSTANT/ZERO/CHECK"));
2692 start_pos=end_pos;
2693 break;
2694 case FIELD_INTERVALL:
2695 global_count=count;
2696 pos=(uchar*) tree_search(&count->int_tree, start_pos,
2697 count->int_tree.custom_arg);
2698 intervall=(uint) (pos - count->tree_buff)/field_length;
2699 DBUG_PRINT("fields", ("FIELD_INTERVALL"));
2700 DBUG_PRINT("fields", ("index: %4u code: 0x%s bits: %2u",
2701 intervall, hexdigits(tree->code[intervall]),
2702 (uint) tree->code_len[intervall]));
2703 write_bits(tree->code[intervall],(uint) tree->code_len[intervall]);
2704 start_pos=end_pos;
2705 break;
2706 case FIELD_BLOB:
2707 {
2708 ulong blob_length=_mi_calc_blob_length(field_length-
2709 portable_sizeof_char_ptr,
2710 start_pos);
2711 /* Empty blobs are encoded with a single 1 bit. */
2712 if (!blob_length)
2713 {
2714 DBUG_PRINT("fields", ("FIELD_BLOB empty, bits: 1"));
2715 write_bits(1,1);
2716 }
2717 else
2718 {
2719 uchar *blob,*blob_end;
2720 DBUG_PRINT("fields", ("FIELD_BLOB not empty, bits: 1"));
2721 write_bits(0,1);
2722 /* Write the blob length. */
2723 DBUG_PRINT("fields", ("FIELD_BLOB %lu bytes, bits: %2u",
2724 blob_length, count->length_bits));
2725 write_bits(blob_length,count->length_bits);
2726 memcpy(&blob, end_pos-portable_sizeof_char_ptr, sizeof(char*));
2727 blob_end=blob+blob_length;
2728 /* Encode the blob bytes. */
2729 for ( ; blob < blob_end ; blob++)
2730 {
2731 DBUG_PRINT("fields",
2732 ("value: 0x%02x code: 0x%s bits: %2u bin: %s",
2733 (uchar) *blob, hexdigits(tree->code[(uchar) *blob]),
2734 (uint) tree->code_len[(uchar) *blob],
2735 bindigits(tree->code[(uchar) *start_pos],
2736 (uint)tree->code_len[(uchar) *start_pos])));
2737 write_bits(tree->code[(uchar) *blob],
2738 (uint) tree->code_len[(uchar) *blob]);
2739 }
2740 tot_blob_length+=blob_length;
2741 }
2742 start_pos= end_pos;
2743 break;
2744 }
2745 case FIELD_VARCHAR:
2746 {
2747 uint var_pack_length= HA_VARCHAR_PACKLENGTH(count->field_length-1);
2748 ulong col_length= (var_pack_length == 1 ?
2749 (uint) *(uchar*) start_pos :
2750 uint2korr(start_pos));
2751 /* Empty varchar are encoded with a single 1 bit. */
2752 if (!col_length)
2753 {
2754 DBUG_PRINT("fields", ("FIELD_VARCHAR empty, bits: 1"));
2755 write_bits(1,1); /* Empty varchar */
2756 }
2757 else
2758 {
2759 uchar *end= start_pos + var_pack_length + col_length;
2760 DBUG_PRINT("fields", ("FIELD_VARCHAR not empty, bits: 1"));
2761 write_bits(0,1);
2762 /* Write the varchar length. */
2763 DBUG_PRINT("fields", ("FIELD_VARCHAR %lu bytes, bits: %2u",
2764 col_length, count->length_bits));
2765 write_bits(col_length,count->length_bits);
2766 /* Encode the varchar bytes. */
2767 for (start_pos+= var_pack_length ; start_pos < end ; start_pos++)
2768 {
2769 DBUG_PRINT("fields",
2770 ("value: 0x%02x code: 0x%s bits: %2u bin: %s",
2771 (uchar) *start_pos,
2772 hexdigits(tree->code[(uchar) *start_pos]),
2773 (uint) tree->code_len[(uchar) *start_pos],
2774 bindigits(tree->code[(uchar) *start_pos],
2775 (uint)tree->code_len[(uchar) *start_pos])));
2776 write_bits(tree->code[(uchar) *start_pos],
2777 (uint) tree->code_len[(uchar) *start_pos]);
2778 }
2779 }
2780 start_pos= end_pos;
2781 break;
2782 }
2783 case FIELD_LAST:
2784 case FIELD_enum_val_count:
2785 abort(); /* Impossible */
2786 }
2787 start_pos+=count->max_zero_fill;
2788 DBUG_PRINT("fields", ("---"));
2789 }
2790 flush_bits();
2791 length=(ulong) ((uchar*) file_buffer.pos - record_pos) - max_pack_length;
2792 pack_length= save_pack_length(pack_version, record_pos, length);
2793 if (pack_blob_length)
2794 pack_length+= save_pack_length(pack_version, record_pos + pack_length,
2795 tot_blob_length);
2796 DBUG_PRINT("fields", ("record: %lu length: %lu blob-length: %lu "
2797 "length-bytes: %lu", (ulong) record_count, length,
2798 tot_blob_length, pack_length));
2799 DBUG_PRINT("fields", ("==="));
2800
2801 /* Correct file buffer if the header was smaller */
2802 if (pack_length != max_pack_length)
2803 {
2804 memmove(record_pos + pack_length, record_pos + max_pack_length, length);
2805 file_buffer.pos-= (max_pack_length-pack_length);
2806 }
2807 if (length < (ulong) min_record_length)
2808 min_record_length=(uint) length;
2809 if (length > (ulong) max_record_length)
2810 max_record_length=(uint) length;
2811 record_count++;
2812 if (write_loop && record_count % WRITE_COUNT == 0)
2813 {
2814 printf("%lu\r", (ulong) record_count);
2815 (void) fflush(stdout);
2816 }
2817 }
2818 else if (error != HA_ERR_RECORD_DELETED)
2819 break;
2820 }
2821 if (error == HA_ERR_END_OF_FILE)
2822 error=0;
2823 else
2824 {
2825 (void) fprintf(stderr, "%s: Got error %d reading records\n",
2826 my_progname, error);
2827 }
2828 if (verbose >= 2)
2829 printf("wrote %s records.\n", llstr((longlong) record_count, llbuf));
2830
2831 mrg->ref_length=max_pack_length;
2832 mrg->min_pack_length=max_record_length ? min_record_length : 0;
2833 mrg->max_pack_length=max_record_length;
2834 DBUG_RETURN(error || error_on_write || flush_buffer(~(ulong) 0));
2835 }
2836
2837
make_new_name(char * new_name,char * old_name)2838 static char *make_new_name(char *new_name, char *old_name)
2839 {
2840 return fn_format(new_name,old_name,"",DATA_TMP_EXT,2+4);
2841 }
2842
make_old_name(char * new_name,char * old_name)2843 static char *make_old_name(char *new_name, char *old_name)
2844 {
2845 return fn_format(new_name,old_name,"",OLD_EXT,2+4);
2846 }
2847
2848 /* rutines for bit writing buffer */
2849
init_file_buffer(File file,pbool read_buffer)2850 static void init_file_buffer(File file, pbool read_buffer)
2851 {
2852 file_buffer.file=file;
2853 file_buffer.buffer= (uchar*) my_malloc(PSI_NOT_INSTRUMENTED,
2854 ALIGN_SIZE(RECORD_CACHE_SIZE),
2855 MYF(MY_WME));
2856 file_buffer.end=file_buffer.buffer+ALIGN_SIZE(RECORD_CACHE_SIZE)-8;
2857 file_buffer.pos_in_file=0;
2858 error_on_write=0;
2859 if (read_buffer)
2860 {
2861
2862 file_buffer.pos=file_buffer.end;
2863 file_buffer.bits=0;
2864 }
2865 else
2866 {
2867 file_buffer.pos=file_buffer.buffer;
2868 file_buffer.bits=BITS_SAVED;
2869 }
2870 file_buffer.bitbucket= 0;
2871 }
2872
2873
flush_buffer(ulong neaded_length)2874 static int flush_buffer(ulong neaded_length)
2875 {
2876 ulong length;
2877
2878 /*
2879 file_buffer.end is 8 bytes lower than the real end of the buffer.
2880 This is done so that the end-of-buffer condition does not need to be
2881 checked for every byte (see write_bits()). Consequently,
2882 file_buffer.pos can become greater than file_buffer.end. The
2883 algorithms in the other functions ensure that there will never be
2884 more than 8 bytes written to the buffer without an end-of-buffer
2885 check. So the buffer cannot be overrun. But we need to check for the
2886 near-to-buffer-end condition to avoid a negative result, which is
2887 casted to unsigned and thus becomes giant.
2888 */
2889 if ((file_buffer.pos < file_buffer.end) &&
2890 ((ulong) (file_buffer.end - file_buffer.pos) > neaded_length))
2891 return 0;
2892 length=(ulong) (file_buffer.pos-file_buffer.buffer);
2893 file_buffer.pos=file_buffer.buffer;
2894 file_buffer.pos_in_file+=length;
2895 if (test_only)
2896 return 0;
2897 if (error_on_write|| my_write(file_buffer.file,
2898 (const uchar*) file_buffer.buffer,
2899 length,
2900 MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)))
2901 {
2902 error_on_write=1;
2903 return 1;
2904 }
2905
2906 if (neaded_length != ~(ulong) 0 &&
2907 (ulong) (file_buffer.end-file_buffer.buffer) < neaded_length)
2908 {
2909 char *tmp;
2910 neaded_length+=256; /* some margin */
2911 tmp= my_realloc(PSI_NOT_INSTRUMENTED,
2912 (char*) file_buffer.buffer, neaded_length,MYF(MY_WME));
2913 if (!tmp)
2914 return 1;
2915 file_buffer.pos= ((uchar*) tmp +
2916 (ulong) (file_buffer.pos - file_buffer.buffer));
2917 file_buffer.buffer= (uchar*) tmp;
2918 file_buffer.end= (uchar*) (tmp+neaded_length-8);
2919 }
2920 return 0;
2921 }
2922
2923
end_file_buffer(void)2924 static void end_file_buffer(void)
2925 {
2926 my_free(file_buffer.buffer);
2927 }
2928
2929 /* output `bits` low bits of `value' */
2930
write_bits(ulonglong value,uint bits)2931 static void write_bits(ulonglong value, uint bits)
2932 {
2933 assert(((bits < 8 * sizeof(value)) && ! (value >> bits)) ||
2934 (bits == 8 * sizeof(value)));
2935
2936 if ((file_buffer.bits-= (int) bits) >= 0)
2937 {
2938 file_buffer.bitbucket|= value << file_buffer.bits;
2939 }
2940 else
2941 {
2942 ulonglong bit_buffer;
2943 bits= (uint) -file_buffer.bits;
2944 bit_buffer= (file_buffer.bitbucket |
2945 ((bits != 8 * sizeof(value)) ? (value >> bits) : 0));
2946 #if BITS_SAVED == 64
2947 *file_buffer.pos++= (uchar) (bit_buffer >> 56);
2948 *file_buffer.pos++= (uchar) (bit_buffer >> 48);
2949 *file_buffer.pos++= (uchar) (bit_buffer >> 40);
2950 *file_buffer.pos++= (uchar) (bit_buffer >> 32);
2951 #endif
2952 *file_buffer.pos++= (uchar) (bit_buffer >> 24);
2953 *file_buffer.pos++= (uchar) (bit_buffer >> 16);
2954 *file_buffer.pos++= (uchar) (bit_buffer >> 8);
2955 *file_buffer.pos++= (uchar) (bit_buffer);
2956
2957 if (bits != 8 * sizeof(value))
2958 value&= (((ulonglong) 1) << bits) - 1;
2959 if (file_buffer.pos >= file_buffer.end)
2960 (void) flush_buffer(~ (ulong) 0);
2961 file_buffer.bits=(int) (BITS_SAVED - bits);
2962 file_buffer.bitbucket= value << (BITS_SAVED - bits);
2963 }
2964 return;
2965 }
2966
2967 /* Flush bits in bit_buffer to buffer */
2968
flush_bits(void)2969 static void flush_bits(void)
2970 {
2971 int bits;
2972 ulonglong bit_buffer;
2973
2974 bits= file_buffer.bits & ~7;
2975 bit_buffer= file_buffer.bitbucket >> bits;
2976 bits= BITS_SAVED - bits;
2977 while (bits > 0)
2978 {
2979 bits-= 8;
2980 *file_buffer.pos++= (uchar) (bit_buffer >> bits);
2981 }
2982 if (file_buffer.pos >= file_buffer.end)
2983 (void) flush_buffer(~ (ulong) 0);
2984 file_buffer.bits= BITS_SAVED;
2985 file_buffer.bitbucket= 0;
2986 }
2987
2988
2989 /****************************************************************************
2990 ** functions to handle the joined files
2991 ****************************************************************************/
2992
save_state(MI_INFO * isam_file,PACK_MRG_INFO * mrg,my_off_t new_length,ha_checksum crc)2993 static int save_state(MI_INFO *isam_file,PACK_MRG_INFO *mrg,my_off_t new_length,
2994 ha_checksum crc)
2995 {
2996 MYISAM_SHARE *share=isam_file->s;
2997 uint options=mi_uint2korr(share->state.header.options);
2998 uint key;
2999 DBUG_ENTER("save_state");
3000
3001 options|= HA_OPTION_COMPRESS_RECORD | HA_OPTION_READ_ONLY_DATA;
3002 mi_int2store(share->state.header.options,options);
3003
3004 share->state.state.data_file_length=new_length;
3005 share->state.state.del=0;
3006 share->state.state.empty=0;
3007 share->state.dellink= HA_OFFSET_ERROR;
3008 share->state.split=(ha_rows) mrg->records;
3009 share->state.version=(ulong) time((time_t*) 0);
3010 if (! mi_is_all_keys_active(share->state.key_map, share->base.keys))
3011 {
3012 /*
3013 Some indexes are disabled, cannot use current key_file_length value
3014 as an estimate of upper bound of index file size. Use packed data file
3015 size instead.
3016 */
3017 share->state.state.key_file_length= new_length;
3018 }
3019 /*
3020 If there are no disabled indexes, keep key_file_length value from
3021 original file so "myisamchk -rq" can use this value (this is necessary
3022 because index size cannot be easily calculated for fulltext keys)
3023 */
3024 mi_clear_all_keys_active(share->state.key_map);
3025 for (key=0 ; key < share->base.keys ; key++)
3026 share->state.key_root[key]= HA_OFFSET_ERROR;
3027 for (key=0 ; key < share->state.header.max_block_size_index ; key++)
3028 share->state.key_del[key]= HA_OFFSET_ERROR;
3029 isam_file->state->checksum=crc; /* Save crc here */
3030 share->changed=1; /* Force write of header */
3031 share->state.open_count=0;
3032 share->global_changed=0;
3033 (void) my_chsize(share->kfile, share->base.keystart, 0, MYF(0));
3034 if (share->base.keys)
3035 isamchk_neaded=1;
3036 DBUG_RETURN(mi_state_info_write(share->kfile,&share->state,1+2));
3037 }
3038
3039
save_state_mrg(File file,PACK_MRG_INFO * mrg,my_off_t new_length,ha_checksum crc)3040 static int save_state_mrg(File file,PACK_MRG_INFO *mrg,my_off_t new_length,
3041 ha_checksum crc)
3042 {
3043 MI_STATE_INFO state;
3044 MI_INFO *isam_file=mrg->file[0];
3045 uint options;
3046 DBUG_ENTER("save_state_mrg");
3047
3048 state= isam_file->s->state;
3049 options= (mi_uint2korr(state.header.options) | HA_OPTION_COMPRESS_RECORD |
3050 HA_OPTION_READ_ONLY_DATA);
3051 mi_int2store(state.header.options,options);
3052 state.state.data_file_length=new_length;
3053 state.state.del=0;
3054 state.state.empty=0;
3055 state.state.records=state.split=(ha_rows) mrg->records;
3056 /* See comment above in save_state about key_file_length handling. */
3057 if (mrg->src_file_has_indexes_disabled)
3058 {
3059 isam_file->s->state.state.key_file_length=
3060 MY_MAX(isam_file->s->state.state.key_file_length, new_length);
3061 }
3062 state.dellink= HA_OFFSET_ERROR;
3063 state.version=(ulong) time((time_t*) 0);
3064 mi_clear_all_keys_active(state.key_map);
3065 state.state.checksum=crc;
3066 if (isam_file->s->base.keys)
3067 isamchk_neaded=1;
3068 state.changed=STATE_CHANGED | STATE_NOT_ANALYZED; /* Force check of table */
3069 DBUG_RETURN (mi_state_info_write(file,&state,1+2));
3070 }
3071
3072
3073 /* reset for mrg_rrnd */
3074
mrg_reset(PACK_MRG_INFO * mrg)3075 static void mrg_reset(PACK_MRG_INFO *mrg)
3076 {
3077 if (mrg->current)
3078 {
3079 mi_extra(*mrg->current, HA_EXTRA_NO_CACHE, 0);
3080 mrg->current=0;
3081 }
3082 }
3083
mrg_rrnd(PACK_MRG_INFO * info,uchar * buf)3084 static int mrg_rrnd(PACK_MRG_INFO *info,uchar *buf)
3085 {
3086 int error;
3087 MI_INFO *isam_info;
3088 my_off_t filepos;
3089
3090 if (!info->current)
3091 {
3092 isam_info= *(info->current=info->file);
3093 info->end=info->current+info->count;
3094 mi_reset(isam_info);
3095 mi_extra(isam_info, HA_EXTRA_CACHE, 0);
3096 filepos=isam_info->s->pack.header_length;
3097 }
3098 else
3099 {
3100 isam_info= *info->current;
3101 filepos= isam_info->nextpos;
3102 }
3103
3104 for (;;)
3105 {
3106 isam_info->update&= HA_STATE_CHANGED;
3107 if (!(error=(*isam_info->s->read_rnd)(isam_info,(uchar*) buf,
3108 filepos, 1)) ||
3109 error != HA_ERR_END_OF_FILE)
3110 return (error);
3111 mi_extra(isam_info,HA_EXTRA_NO_CACHE, 0);
3112 if (info->current+1 == info->end)
3113 return(HA_ERR_END_OF_FILE);
3114 info->current++;
3115 isam_info= *info->current;
3116 filepos=isam_info->s->pack.header_length;
3117 mi_reset(isam_info);
3118 mi_extra(isam_info,HA_EXTRA_CACHE, 0);
3119 }
3120 }
3121
3122
mrg_close(PACK_MRG_INFO * mrg)3123 static int mrg_close(PACK_MRG_INFO *mrg)
3124 {
3125 uint i;
3126 int error=0;
3127 for (i=0 ; i < mrg->count ; i++)
3128 error|=mi_close(mrg->file[i]);
3129 if (mrg->free_file)
3130 my_free(mrg->file);
3131 return error;
3132 }
3133
3134
3135 #if !defined(NDEBUG)
3136 /*
3137 Fake the counts to get big Huffman codes.
3138
3139 SYNOPSIS
3140 fakebigcodes()
3141 huff_counts A pointer to the counts array.
3142 end_count A pointer past the counts array.
3143
3144 DESCRIPTION
3145
3146 Huffman coding works by removing the two least frequent values from
3147 the list of values and add a new value with the sum of their
3148 incidences in a loop until only one value is left. Every time a
3149 value is reused for a new value, it gets one more bit for its
3150 encoding. Hence, the least frequent values get the longest codes.
3151
3152 To get a maximum code length for a value, two of the values must
3153 have an incidence of 1. As their sum is 2, the next infrequent value
3154 must have at least an incidence of 2, then 4, 8, 16 and so on. This
3155 means that one needs 2**n bytes (values) for a code length of n
3156 bits. However, using more distinct values forces the use of longer
3157 codes, or reaching the code length with less total bytes (values).
3158
3159 To get 64(32)-bit codes, I sort the counts by decreasing incidence.
3160 I assign counts of 1 to the two most frequent values, a count of 2
3161 for the next one, then 4, 8, and so on until 2**64-1(2**30-1). All
3162 the remaining values get 1. That way every possible byte has an
3163 assigned code, though not all codes are used if not all byte values
3164 are present in the column.
3165
3166 This strategy would work with distinct column values too, but
3167 requires that at least 64(32) values are present. To make things
3168 easier here, I cancel all distinct column values and force byte
3169 compression for all columns.
3170
3171 RETURN
3172 void
3173 */
3174
fakebigcodes(HUFF_COUNTS * huff_counts,HUFF_COUNTS * end_count)3175 static void fakebigcodes(HUFF_COUNTS *huff_counts, HUFF_COUNTS *end_count)
3176 {
3177 HUFF_COUNTS *count;
3178 my_off_t *cur_count_p;
3179 my_off_t *end_count_p;
3180 my_off_t **cur_sort_p;
3181 my_off_t **end_sort_p;
3182 my_off_t *sort_counts[256];
3183 my_off_t total;
3184 DBUG_ENTER("fakebigcodes");
3185
3186 for (count= huff_counts; count < end_count; count++)
3187 {
3188 /*
3189 Remove distinct column values.
3190 */
3191 if (huff_counts->tree_buff)
3192 {
3193 my_free(huff_counts->tree_buff);
3194 delete_tree(&huff_counts->int_tree);
3195 huff_counts->tree_buff= NULL;
3196 DBUG_PRINT("fakebigcodes", ("freed distinct column values"));
3197 }
3198
3199 /*
3200 Sort counts by decreasing incidence.
3201 */
3202 cur_count_p= count->counts;
3203 end_count_p= cur_count_p + 256;
3204 cur_sort_p= sort_counts;
3205 while (cur_count_p < end_count_p)
3206 *(cur_sort_p++)= cur_count_p++;
3207 (void) my_qsort(sort_counts, 256, sizeof(my_off_t*), (qsort_cmp) fakecmp);
3208
3209 /*
3210 Assign faked counts.
3211 */
3212 cur_sort_p= sort_counts;
3213 #if SIZEOF_LONG_LONG > 4
3214 end_sort_p= sort_counts + 8 * sizeof(ulonglong) - 1;
3215 #else
3216 end_sort_p= sort_counts + 8 * sizeof(ulonglong) - 2;
3217 #endif
3218 /* Most frequent value gets a faked count of 1. */
3219 **(cur_sort_p++)= 1;
3220 total= 1;
3221 while (cur_sort_p < end_sort_p)
3222 {
3223 **(cur_sort_p++)= total;
3224 total<<= 1;
3225 }
3226 /* Set the last value. */
3227 **(cur_sort_p++)= --total;
3228 /*
3229 Set the remaining counts.
3230 */
3231 end_sort_p= sort_counts + 256;
3232 while (cur_sort_p < end_sort_p)
3233 **(cur_sort_p++)= 1;
3234 }
3235 DBUG_VOID_RETURN;
3236 }
3237
3238
3239 /*
3240 Compare two counts for reverse sorting.
3241
3242 SYNOPSIS
3243 fakecmp()
3244 count1 One count.
3245 count2 Another count.
3246
3247 RETURN
3248 1 count1 < count2
3249 0 count1 == count2
3250 -1 count1 > count2
3251 */
3252
fakecmp(my_off_t ** count1,my_off_t ** count2)3253 static int fakecmp(my_off_t **count1, my_off_t **count2)
3254 {
3255 return ((**count1 < **count2) ? 1 :
3256 (**count1 > **count2) ? -1 : 0);
3257 }
3258 #endif
3259
3260 #include "mi_extrafunc.h"
3261