myisampack.c 100 KB
Newer Older
unknown's avatar
unknown committed
1
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
unknown's avatar
unknown committed
2

unknown's avatar
unknown committed
3 4 5 6
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
unknown's avatar
unknown committed
7

unknown's avatar
unknown committed
8 9 10 11
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
unknown's avatar
unknown committed
12

unknown's avatar
unknown committed
13 14 15 16 17
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

/* Pack MyISAM file */
unknown's avatar
unknown committed
18 19

#ifndef USE_MY_FUNC
unknown's avatar
unknown committed
20
#define USE_MY_FUNC			/* We need at least my_malloc */
unknown's avatar
unknown committed
21 22 23 24 25 26 27 28 29 30
#endif

#include "myisamdef.h"
#include <queues.h>
#include <my_tree.h>
#include "mysys_err.h"
#ifdef MSDOS
#include <io.h>
#endif
#ifndef __GNU_LIBRARY__
unknown's avatar
unknown committed
31
#define __GNU_LIBRARY__			/* Skip warnings in getopt.h */
unknown's avatar
unknown committed
32
#endif
33
#include <my_getopt.h>
34
#include <assert.h>
unknown's avatar
unknown committed
35

36 37
#if SIZEOF_LONG_LONG > 4
#define BITS_SAVED 64
unknown's avatar
unknown committed
38
#else
39
#define BITS_SAVED 32
unknown's avatar
unknown committed
40 41 42 43 44 45 46 47 48 49 50 51
#endif

#define IS_OFFSET ((uint) 32768)	/* Bit if offset or char in tree */
#define HEAD_LENGTH	32
#define ALLOWED_JOIN_DIFF	256	/* Diff allowed to join trees */

#define DATA_TMP_EXT		".TMD"
#define OLD_EXT			".OLD"
#define WRITE_COUNT		MY_HOW_OFTEN_TO_WRITE

struct st_file_buffer {
  File file;
52
  uchar *buffer,*pos,*end;
unknown's avatar
unknown committed
53 54
  my_off_t pos_in_file;
  int bits;
55
  ulonglong bitbucket;
unknown's avatar
unknown committed
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
};

struct st_huff_tree;
struct st_huff_element;

typedef struct st_huff_counts {
  uint	field_length,max_zero_fill;
  uint	pack_type;
  uint	max_end_space,max_pre_space,length_bits,min_space;
  ulong max_length;
  enum en_fieldtype field_type;
  struct st_huff_tree *tree;		/* Tree for field */
  my_off_t counts[256];
  my_off_t end_space[8];
  my_off_t pre_space[8];
  my_off_t tot_end_space,tot_pre_space,zero_fields,empty_fields,bytes_packed;
72 73 74
  TREE int_tree;        /* Tree for detecting distinct column values. */
  byte *tree_buff;      /* Column values, 'field_length' each. */
  byte *tree_pos;       /* Points to end of column values in 'tree_buff'. */
unknown's avatar
unknown committed
75 76 77 78
} HUFF_COUNTS;

typedef struct st_huff_element HUFF_ELEMENT;

79 80 81 82
/*
  WARNING: It is crucial for the optimizations in calc_packed_length()
  that 'count' is the first element of 'HUFF_ELEMENT'.
*/
unknown's avatar
unknown committed
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
struct st_huff_element {
  my_off_t count;
  union un_element {
    struct st_nod {
      HUFF_ELEMENT *left,*right;
    } nod;
    struct st_leaf {
      HUFF_ELEMENT *null;
      uint	element_nr;		/* Number of element */
    } leaf;
  } a;
};


typedef struct st_huff_tree {
  HUFF_ELEMENT *root,*element_buffer;
  HUFF_COUNTS *counts;
  uint tree_number;
  uint elements;
  my_off_t bytes_packed;
  uint tree_pack_length;
  uint min_chr,max_chr,char_bits,offset_bits,max_offset,height;
105
  ulonglong *code;
unknown's avatar
unknown committed
106 107 108 109 110 111 112 113 114 115 116 117 118
  uchar *code_len;
} HUFF_TREE;


typedef struct st_isam_mrg {
  MI_INFO **file,**current,**end;
  uint free_file;
  uint count;
  uint	min_pack_length;		/* Theese is used by packed data */
  uint	max_pack_length;
  uint	ref_length;
  uint	max_blob_length;
  my_off_t records;
unknown's avatar
unknown committed
119 120
  /* true if at least one source file has at least one disabled index */
  my_bool src_file_has_indexes_disabled;
unknown's avatar
unknown committed
121
} PACK_MRG_INFO;
unknown's avatar
unknown committed
122 123 124 125 126


extern int main(int argc,char * *argv);
static void get_options(int *argc,char ***argv);
static MI_INFO *open_isam_file(char *name,int mode);
unknown's avatar
unknown committed
127 128
static bool open_isam_files(PACK_MRG_INFO *mrg,char **names,uint count);
static int compress(PACK_MRG_INFO *file,char *join_name);
unknown's avatar
unknown committed
129 130 131 132 133
static HUFF_COUNTS *init_huff_count(MI_INFO *info,my_off_t records);
static void free_counts_and_tree_and_queue(HUFF_TREE *huff_trees,
					   uint trees,
					   HUFF_COUNTS *huff_counts,
					   uint fields);
134 135
static int compare_tree(void* cmp_arg __attribute__((unused)),
			const uchar *s,const uchar *t);
unknown's avatar
unknown committed
136
static int get_statistic(PACK_MRG_INFO *mrg,HUFF_COUNTS *huff_counts);
unknown's avatar
unknown committed
137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
static void check_counts(HUFF_COUNTS *huff_counts,uint trees,
			 my_off_t records);
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);
static HUFF_TREE* make_huff_trees(HUFF_COUNTS *huff_counts,uint trees);
static int make_huff_tree(HUFF_TREE *tree,HUFF_COUNTS *huff_counts);
static int compare_huff_elements(void *not_used, byte *a,byte *b);
static int save_counts_in_queue(byte *key,element_count count,
				    HUFF_TREE *tree);
static my_off_t calc_packed_length(HUFF_COUNTS *huff_counts,uint flag);
static uint join_same_trees(HUFF_COUNTS *huff_counts,uint trees);
static int make_huff_decode_table(HUFF_TREE *huff_tree,uint trees);
static void make_traverse_code_tree(HUFF_TREE *huff_tree,
				    HUFF_ELEMENT *element,uint size,
153
				    ulonglong code);
unknown's avatar
unknown committed
154
static int write_header(PACK_MRG_INFO *isam_file, uint header_length,uint trees,
unknown's avatar
unknown committed
155 156 157 158 159 160 161
			my_off_t tot_elements,my_off_t filelength);
static void write_field_info(HUFF_COUNTS *counts, uint fields,uint trees);
static my_off_t write_huff_tree(HUFF_TREE *huff_tree,uint trees);
static uint *make_offset_code_tree(HUFF_TREE *huff_tree,
				       HUFF_ELEMENT *element,
				       uint *offset);
static uint max_bit(uint value);
unknown's avatar
unknown committed
162
static int compress_isam_file(PACK_MRG_INFO *file,HUFF_COUNTS *huff_counts);
unknown's avatar
unknown committed
163 164 165 166 167
static char *make_new_name(char *new_name,char *old_name);
static char *make_old_name(char *new_name,char *old_name);
static void init_file_buffer(File file,pbool read_buffer);
static int flush_buffer(ulong neaded_length);
static void end_file_buffer(void);
168
static void write_bits(ulonglong value, uint bits);
unknown's avatar
unknown committed
169
static void flush_bits(void);
unknown's avatar
unknown committed
170
static int save_state(MI_INFO *isam_file,PACK_MRG_INFO *mrg,my_off_t new_length,
unknown's avatar
unknown committed
171
		      ha_checksum crc);
unknown's avatar
unknown committed
172
static int save_state_mrg(File file,PACK_MRG_INFO *isam_file,my_off_t new_length,
unknown's avatar
unknown committed
173
			  ha_checksum crc);
unknown's avatar
unknown committed
174 175 176
static int mrg_close(PACK_MRG_INFO *mrg);
static int mrg_rrnd(PACK_MRG_INFO *info,byte *buf);
static void mrg_reset(PACK_MRG_INFO *mrg);
177 178 179 180
#if !defined(DBUG_OFF)
static void fakebigcodes(HUFF_COUNTS *huff_counts, HUFF_COUNTS *end_count);
static int fakecmp(my_off_t **count1, my_off_t **count2);
#endif
unknown's avatar
unknown committed
181 182


183 184
static int error_on_write=0,test_only=0,verbose=0,silent=0,
	   write_loop=0,force_pack=0, isamchk_neaded=0;
unknown's avatar
unknown committed
185
static int tmpfile_createflag=O_RDWR | O_TRUNC | O_EXCL;
186
static my_bool backup, opt_wait;
187 188 189 190 191 192 193
/*
  tree_buff_length is somewhat arbitrary. The bigger it is the better
  the chance to win in terms of compression factor. On the other hand,
  this table becomes part of the compressed file header. And its length
  is coded with 16 bits in the header. Hence the limit is 2**16 - 1.
*/
static uint tree_buff_length= 65536 - MALLOC_OVERHEAD;
unknown's avatar
unknown committed
194 195 196 197 198 199 200 201 202 203 204 205 206 207
static char tmp_dir[FN_REFLEN]={0},*join_table;
static my_off_t intervall_length;
static ha_checksum glob_crc;
static struct st_file_buffer file_buffer;
static QUEUE queue;
static HUFF_COUNTS *global_count;
static char zero_string[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
static const char *load_default_groups[]= { "myisampack",0 };

	/* The main program */

int main(int argc, char **argv)
{
  int error,ok;
unknown's avatar
unknown committed
208
  PACK_MRG_INFO merge;
unknown's avatar
unknown committed
209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241
  char **default_argv;
  MY_INIT(argv[0]);

  load_defaults("my",load_default_groups,&argc,&argv);
  default_argv= argv;
  get_options(&argc,&argv);

  error=ok=isamchk_neaded=0;
  if (join_table)
  {						/* Join files into one */
    if (open_isam_files(&merge,argv,(uint) argc) ||
	compress(&merge,join_table))
      error=1;
  }
  else while (argc--)
  {
    MI_INFO *isam_file;
    if (!(isam_file=open_isam_file(*argv++,O_RDWR)))
      error=1;
    else
    {
      merge.file= &isam_file;
      merge.current=0;
      merge.free_file=0;
      merge.count=1;
      if (compress(&merge,0))
	error=1;
      else
	ok=1;
    }
  }
  if (ok && isamchk_neaded && !silent)
    puts("Remember to run myisamchk -rq on compressed tables");
242 243
  VOID(fflush(stdout));
  VOID(fflush(stderr));
unknown's avatar
unknown committed
244 245 246 247 248 249 250 251
  free_defaults(default_argv);
  my_end(verbose ? MY_CHECK_ERROR | MY_GIVE_INFO : MY_CHECK_ERROR);
  exit(error ? 2 : 0);
#ifndef _lint
  return 0;					/* No compiler warning */
#endif
}

252
enum options_mp {OPT_CHARSETS_DIR_MP=256};
unknown's avatar
unknown committed
253

254
static struct my_option my_long_options[] =
unknown's avatar
unknown committed
255
{
256
  {"backup", 'b', "Make a backup of the table as table_name.OLD.",
257 258 259 260
   (gptr*) &backup, (gptr*) &backup, 0, GET_BOOL, NO_ARG, 0, 0, 0, 0, 0, 0},
  {"character-sets-dir", OPT_CHARSETS_DIR_MP,
   "Directory where character sets are.", (gptr*) &charsets_dir,
   (gptr*) &charsets_dir, 0, GET_STR, REQUIRED_ARG, 0, 0, 0, 0, 0, 0},
261
  {"debug", '#', "Output debug log. Often this is 'd:t:o,filename'.",
262 263
   0, 0, 0, GET_STR, OPT_ARG, 0, 0, 0, 0, 0, 0},
  {"force", 'f',
unknown's avatar
unknown committed
264
   "Force packing of table even if it gets bigger or if tempfile exists.",
265 266 267 268 269 270 271 272 273 274 275 276 277
   0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
  {"join", 'j',
   "Join all given tables into 'new_table_name'. All tables MUST have identical layouts.",
   (gptr*) &join_table, (gptr*) &join_table, 0, GET_STR, REQUIRED_ARG, 0, 0, 0,
   0, 0, 0},
  {"help", '?', "Display this help and exit.",
   0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
  {"silent", 's', "Be more silent.",
   0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
  {"tmpdir", 'T', "Use temporary directory to store temporary table.",
   0, 0, 0, GET_STR, REQUIRED_ARG, 0, 0, 0, 0, 0, 0},
  {"test", 't', "Don't pack table, only test packing it.",
   0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
278
  {"verbose", 'v', "Write info about progress and packing result. Use many -v for more verbosity!",
279 280 281 282 283 284
   0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
  {"version", 'V', "Output version information and exit.",
   0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
  {"wait", 'w', "Wait and retry if table is in use.", (gptr*) &opt_wait,
   (gptr*) &opt_wait, 0, GET_BOOL, NO_ARG, 0, 0, 0, 0, 0, 0},
  { 0, 0, 0, 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0}
unknown's avatar
unknown committed
285 286
};

unknown's avatar
unknown committed
287
#include <help_start.h>
288

unknown's avatar
unknown committed
289 290
static void print_version(void)
{
291 292
  VOID(printf("%s Ver 1.22 for %s on %s\n",
              my_progname, SYSTEM_TYPE, MACHINE_TYPE));
unknown's avatar
unknown committed
293
  NETWARE_SET_SCREEN_MODE(1);
unknown's avatar
unknown committed
294 295
}

unknown's avatar
unknown committed
296

unknown's avatar
unknown committed
297 298 299
static void usage(void)
{
  print_version();
unknown's avatar
unknown committed
300
  puts("Copyright (C) 2002 MySQL AB");
unknown's avatar
unknown committed
301 302 303 304 305 306
  puts("This software comes with ABSOLUTELY NO WARRANTY. This is free software,");
  puts("and you are welcome to modify and redistribute it under the GPL license\n");

  puts("Pack a MyISAM-table to take much less space.");
  puts("Keys are not updated, you must run myisamchk -rq on the datafile");
  puts("afterwards to update the keys.");
307
  puts("You should give the .MYI file as the filename argument.");
unknown's avatar
unknown committed
308

309
  VOID(printf("\nUsage: %s [OPTIONS] filename...\n", my_progname));
310 311 312 313 314
  my_print_help(my_long_options);
  print_defaults("my", load_default_groups);
  my_print_variables(my_long_options);
}

unknown's avatar
unknown committed
315
#include <help_end.h>
316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332

static my_bool
get_one_option(int optid, const struct my_option *opt __attribute__((unused)),
	       char *argument)
{
  uint length;

  switch(optid) {
  case 'f':
    force_pack= 1;
    tmpfile_createflag= O_RDWR | O_TRUNC;
    break;
  case 's':
    write_loop= verbose= 0;
    silent= 1;
    break;
  case 't':
333 334 335 336
    test_only= 1;
    /* Avoid to reset 'verbose' if it was already set > 1. */
    if (! verbose)
      verbose= 1;
337 338 339 340 341 342 343 344 345 346
    break;
  case 'T':
    length= (uint) (strmov(tmp_dir, argument) - tmp_dir);
    if (length != dirname_length(tmp_dir))
    {
      tmp_dir[length]=FN_LIBCHAR;
      tmp_dir[length+1]=0;
    }
    break;
  case 'v':
347
    verbose++; /* Allow for selecting the level of verbosity. */
348 349 350 351 352 353 354 355 356 357 358 359 360 361
    silent= 0;
    break;
  case '#':
    DBUG_PUSH(argument ? argument : "d:t:o");
    break;
  case 'V':
    print_version();
    exit(0);
  case 'I':
  case '?':
    usage();
    exit(0);
  }
  return 0;
362
}
unknown's avatar
unknown committed
363 364 365 366 367 368

	/* reads options */
	/* Initiates DEBUG - but no debugging here ! */

static void get_options(int *argc,char ***argv)
{
369
  int ho_error;
unknown's avatar
unknown committed
370 371 372 373 374

  my_progname= argv[0][0];
  if (isatty(fileno(stdout)))
    write_loop=1;

375
  if ((ho_error=handle_options(argc, argv, my_long_options, get_one_option)))
376 377
    exit(ho_error);

unknown's avatar
unknown committed
378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401
  if (!*argc)
  {
    usage();
    exit(1);
  }
  if (join_table)
  {
    backup=0;					/* Not needed */
    tmp_dir[0]=0;
  }
  return;
}


static MI_INFO *open_isam_file(char *name,int mode)
{
  MI_INFO *isam_file;
  MYISAM_SHARE *share;
  DBUG_ENTER("open_isam_file");

  if (!(isam_file=mi_open(name,mode,
			  (opt_wait ? HA_OPEN_WAIT_IF_LOCKED :
			   HA_OPEN_ABORT_IF_LOCKED))))
  {
402
    VOID(fprintf(stderr, "%s gave error %d on open\n", name, my_errno));
unknown's avatar
unknown committed
403 404 405 406 407 408 409
    DBUG_RETURN(0);
  }
  share=isam_file->s;
  if (share->options & HA_OPTION_COMPRESS_RECORD && !join_table)
  {
    if (!force_pack)
    {
410
      VOID(fprintf(stderr, "%s is already compressed\n", name));
unknown's avatar
unknown committed
411 412 413 414 415 416 417 418 419 420 421
      VOID(mi_close(isam_file));
      DBUG_RETURN(0);
    }
    if (verbose)
      puts("Recompressing already compressed table");
    share->options&= ~HA_OPTION_READ_ONLY_DATA; /* We are modifing it */
  }
  if (! force_pack && share->state.state.records != 0 &&
      (share->state.state.records <= 1 ||
       share->state.state.data_file_length < 1024))
  {
422
    VOID(fprintf(stderr, "%s is too small to compress\n", name));
unknown's avatar
unknown committed
423 424 425 426 427 428 429 430
    VOID(mi_close(isam_file));
    DBUG_RETURN(0);
  }
  VOID(mi_lock_database(isam_file,F_WRLCK));
  DBUG_RETURN(isam_file);
}


unknown's avatar
unknown committed
431
static bool open_isam_files(PACK_MRG_INFO *mrg,char **names,uint count)
unknown's avatar
unknown committed
432 433 434 435 436 437
{
  uint i,j;
  mrg->count=0;
  mrg->current=0;
  mrg->file=(MI_INFO**) my_malloc(sizeof(MI_INFO*)*count,MYF(MY_FAE));
  mrg->free_file=1;
unknown's avatar
unknown committed
438
  mrg->src_file_has_indexes_disabled= 0;
unknown's avatar
unknown committed
439 440 441 442
  for (i=0; i < count ; i++)
  {
    if (!(mrg->file[i]=open_isam_file(names[i],O_RDONLY)))
      goto error;
443 444 445 446

    mrg->src_file_has_indexes_disabled|= ((mrg->file[i]->s->state.key_map != 
                                           (((ulonglong) 1) <<
                                            mrg->file[i]->s->base. keys) - 1));
unknown's avatar
unknown committed
447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467
  }
  /* Check that files are identical */
  for (j=0 ; j < count-1 ; j++)
  {
    MI_COLUMNDEF *m1,*m2,*end;
    if (mrg->file[j]->s->base.reclength != mrg->file[j+1]->s->base.reclength ||
	mrg->file[j]->s->base.fields != mrg->file[j+1]->s->base.fields)
      goto diff_file;
    m1=mrg->file[j]->s->rec;
    end=m1+mrg->file[j]->s->base.fields;
    m2=mrg->file[j+1]->s->rec;
    for ( ; m1 != end ; m1++,m2++)
    {
      if (m1->type != m2->type || m1->length != m2->length)
	goto diff_file;
    }
  }
  mrg->count=count;
  return 0;

 diff_file:
468 469
  VOID(fprintf(stderr, "%s: Tables '%s' and '%s' are not identical\n",
               my_progname, names[j], names[j+1]));
unknown's avatar
unknown committed
470 471 472 473 474 475 476 477
 error:
  while (i--)
    mi_close(mrg->file[i]);
  my_free((gptr) mrg->file,MYF(0));
  return 1;
}


unknown's avatar
unknown committed
478
static int compress(PACK_MRG_INFO *mrg,char *result_table)
unknown's avatar
unknown committed
479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539
{
  int error;
  File new_file,join_isam_file;
  MI_INFO *isam_file;
  MYISAM_SHARE *share;
  char org_name[FN_REFLEN],new_name[FN_REFLEN],temp_name[FN_REFLEN];
  uint i,header_length,fields,trees,used_trees;
  my_off_t old_length,new_length,tot_elements;
  HUFF_COUNTS *huff_counts;
  HUFF_TREE *huff_trees;
  DBUG_ENTER("compress");

  isam_file=mrg->file[0];			/* Take this as an example */
  share=isam_file->s;
  new_file=join_isam_file= -1;
  trees=fields=0;
  huff_trees=0;
  huff_counts=0;

  /* Create temporary or join file */

  if (backup)
    VOID(fn_format(org_name,isam_file->filename,"",MI_NAME_DEXT,2));
  else
    VOID(fn_format(org_name,isam_file->filename,"",MI_NAME_DEXT,2+4+16));
  if (!test_only && result_table)
  {
    /* Make a new indexfile based on first file in list */
    uint length;
    char *buff;
    strmov(org_name,result_table);		/* Fix error messages */
    VOID(fn_format(new_name,result_table,"",MI_NAME_IEXT,2));
    if ((join_isam_file=my_create(new_name,0,tmpfile_createflag,MYF(MY_WME)))
	< 0)
      goto err;
    length=(uint) share->base.keystart;
    if (!(buff=my_malloc(length,MYF(MY_WME))))
      goto err;
    if (my_pread(share->kfile,buff,length,0L,MYF(MY_WME | MY_NABP)) ||
	my_write(join_isam_file,buff,length,
		 MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)))
    {
      my_free(buff,MYF(0));
      goto err;
    }
    my_free(buff,MYF(0));
    VOID(fn_format(new_name,result_table,"",MI_NAME_DEXT,2));
  }
  else if (!tmp_dir[0])
    VOID(make_new_name(new_name,org_name));
  else
    VOID(fn_format(new_name,org_name,tmp_dir,DATA_TMP_EXT,1+2+4));
  if (!test_only &&
      (new_file=my_create(new_name,0,tmpfile_createflag,MYF(MY_WME))) < 0)
    goto err;

  /* Start calculating statistics */

  mrg->records=0;
  for (i=0 ; i < mrg->count ; i++)
    mrg->records+=mrg->file[i]->s->state.state.records;
540 541 542 543

  DBUG_PRINT("info", ("Compressing %s: (%lu records)",
                      result_table ? new_name : org_name,
                      (ulong) mrg->records));
unknown's avatar
unknown committed
544 545
  if (write_loop || verbose)
  {
546 547
    VOID(printf("Compressing %s: (%lu records)\n",
                result_table ? new_name : org_name, (ulong) mrg->records));
unknown's avatar
unknown committed
548 549 550 551
  }
  trees=fields=share->base.fields;
  huff_counts=init_huff_count(isam_file,mrg->records);
  QUICK_SAFEMALLOC;
552 553 554 555 556

  /*
    Read the whole data file(s) for statistics.
  */
  DBUG_PRINT("info", ("- Calculating statistics"));
unknown's avatar
unknown committed
557
  if (write_loop || verbose)
558
    VOID(printf("- Calculating statistics\n"));
unknown's avatar
unknown committed
559 560 561 562 563 564 565 566
  if (get_statistic(mrg,huff_counts))
    goto err;
  NORMAL_SAFEMALLOC;
  old_length=0;
  for (i=0; i < mrg->count ; i++)
    old_length+= (mrg->file[i]->s->state.state.data_file_length -
		  mrg->file[i]->s->state.state.empty);

567 568 569 570
  /*
    Create a global priority queue in preparation for making 
    temporary Huffman trees.
  */
unknown's avatar
unknown committed
571 572
  if (init_queue(&queue,256,0,0,compare_huff_elements,0))
    goto err;
573 574 575 576 577

  /*
    Check each column if we should use pre-space-compress, end-space-
    compress, empty-field-compress or zero-field-compress.
  */
unknown's avatar
unknown committed
578
  check_counts(huff_counts,fields,mrg->records);
579 580 581 582

  /*
    Build a Huffman tree for each column.
  */
unknown's avatar
unknown committed
583
  huff_trees=make_huff_trees(huff_counts,trees);
584 585 586 587 588 589 590

  /*
    If the packed lengths of combined columns is less then the sum of
    the non-combined columns, then create common Huffman trees for them.
    We do this only for byte compressed columns, not for distinct values
    compressed columns.
  */
unknown's avatar
unknown committed
591 592
  if ((int) (used_trees=join_same_trees(huff_counts,trees)) < 0)
    goto err;
593 594 595 596

  /*
    Assign codes to all byte or column values.
  */
unknown's avatar
unknown committed
597 598 599
  if (make_huff_decode_table(huff_trees,fields))
    goto err;

600
  /* Prepare a file buffer. */
unknown's avatar
unknown committed
601
  init_file_buffer(new_file,0);
602 603 604 605

  /*
    Reserve space in the target file for the fixed compressed file header.
  */
unknown's avatar
unknown committed
606 607 608 609
  file_buffer.pos_in_file=HEAD_LENGTH;
  if (! test_only)
    VOID(my_seek(new_file,file_buffer.pos_in_file,MY_SEEK_SET,MYF(0)));

610 611 612
  /*
    Write field infos: field type, pack type, length bits, tree number.
  */
unknown's avatar
unknown committed
613
  write_field_info(huff_counts,fields,used_trees);
614 615 616 617

  /*
    Write decode trees.
  */
unknown's avatar
unknown committed
618 619
  if (!(tot_elements=write_huff_tree(huff_trees,trees)))
    goto err;
620 621 622 623 624 625

  /*
    Calculate the total length of the compression info header.
    This includes the fixed compressed file header, the column compression
    type descriptions, and the decode trees.
  */
unknown's avatar
unknown committed
626 627 628
  header_length=(uint) file_buffer.pos_in_file+
    (uint) (file_buffer.pos-file_buffer.buffer);

629 630 631 632
  /*
    Compress the source file into the target file.
  */
  DBUG_PRINT("info", ("- Compressing file"));
unknown's avatar
unknown committed
633
  if (write_loop || verbose)
634
    VOID(printf("- Compressing file\n"));
unknown's avatar
unknown committed
635 636 637 638 639 640 641 642 643
  error=compress_isam_file(mrg,huff_counts);
  new_length=file_buffer.pos_in_file;
  if (!error && !test_only)
  {
    char buff[MEMMAP_EXTRA_MARGIN];		/* End marginal for memmap */
    bzero(buff,sizeof(buff));
    error=my_write(file_buffer.file,buff,sizeof(buff),
		   MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)) != 0;
  }
644 645 646 647

  /*
    Write the fixed compressed file header.
  */
unknown's avatar
unknown committed
648 649 650
  if (!error)
    error=write_header(mrg,header_length,used_trees,tot_elements,
		       new_length);
651 652

  /* Flush the file buffer. */
unknown's avatar
unknown committed
653 654
  end_file_buffer();

655 656 657 658 659
  /* Display statistics. */
  DBUG_PRINT("info", ("Min record length: %6d  Max length: %6d  "
                      "Mean total length: %6ld\n",
                      mrg->min_pack_length, mrg->max_pack_length,
                      (ulong) (mrg->records ? (new_length/mrg->records) : 0)));
unknown's avatar
unknown committed
660
  if (verbose && mrg->records)
661 662 663
    VOID(printf("Min record length: %6d   Max length: %6d   "
                "Mean total length: %6ld\n", mrg->min_pack_length,
                mrg->max_pack_length, (ulong) (new_length/mrg->records)));
unknown's avatar
unknown committed
664

665
  /* Close source and target file. */
unknown's avatar
unknown committed
666 667 668 669 670 671 672 673 674 675
  if (!test_only)
  {
    error|=my_close(new_file,MYF(MY_WME));
    if (!result_table)
    {
      error|=my_close(isam_file->dfile,MYF(MY_WME));
      isam_file->dfile= -1;		/* Tell mi_close file is closed */
    }
  }

676
  /* Cleanup. */
unknown's avatar
unknown committed
677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693
  free_counts_and_tree_and_queue(huff_trees,trees,huff_counts,fields);
  if (! test_only && ! error)
  {
    if (result_table)
    {
      error=save_state_mrg(join_isam_file,mrg,new_length,glob_crc);
    }
    else
    {
      if (backup)
      {
	if (my_rename(org_name,make_old_name(temp_name,isam_file->filename),
		      MYF(MY_WME)))
	  error=1;
	else
	{
	  if (tmp_dir[0])
694
	    error=my_copy(new_name,org_name,MYF(MY_WME));
unknown's avatar
unknown committed
695 696 697 698 699 700 701 702 703
	  else
	    error=my_rename(new_name,org_name,MYF(MY_WME));
	  if (!error)
	    VOID(my_copystat(temp_name,org_name,MYF(MY_COPYTIME)));
	}
      }
      else
      {
	if (tmp_dir[0])
704 705
	  error=my_copy(new_name,org_name,
			MYF(MY_WME | MY_HOLD_ORIGINAL_MODES | MY_COPYTIME));
unknown's avatar
unknown committed
706 707 708 709 710 711 712 713 714 715 716 717
	else
	  error=my_redel(org_name,new_name,MYF(MY_WME | MY_COPYTIME));
      }
      if (! error)
	error=save_state(isam_file,mrg,new_length,glob_crc);
    }
  }
  error|=mrg_close(mrg);
  if (join_isam_file >= 0)
    error|=my_close(join_isam_file,MYF(MY_WME));
  if (error)
  {
718
    VOID(fprintf(stderr, "Aborting: %s is not compressed\n", org_name));
719
    VOID(my_delete(new_name,MYF(MY_WME)));
unknown's avatar
unknown committed
720 721 722 723 724
    DBUG_RETURN(-1);
  }
  if (write_loop || verbose)
  {
    if (old_length)
725 726 727
      VOID(printf("%.4g%%     \n",
                  (((longlong) (old_length - new_length)) * 100.0 /
                   (longlong) old_length)));
unknown's avatar
unknown committed
728 729 730 731 732 733 734 735 736 737 738 739
    else
      puts("Empty file saved in compressed format");
  }
  DBUG_RETURN(0);

 err:
  free_counts_and_tree_and_queue(huff_trees,trees,huff_counts,fields);
  if (new_file >= 0)
    VOID(my_close(new_file,MYF(0)));
  if (join_isam_file >= 0)
    VOID(my_close(join_isam_file,MYF(0)));
  mrg_close(mrg);
740
  VOID(fprintf(stderr, "Aborted: %s is not compressed\n", org_name));
unknown's avatar
unknown committed
741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764
  DBUG_RETURN(-1);
}

	/* Init a huff_count-struct for each field and init it */

static HUFF_COUNTS *init_huff_count(MI_INFO *info,my_off_t records)
{
  reg2 uint i;
  reg1 HUFF_COUNTS *count;
  if ((count = (HUFF_COUNTS*) my_malloc(info->s->base.fields*
					sizeof(HUFF_COUNTS),
					MYF(MY_ZEROFILL | MY_WME))))
  {
    for (i=0 ; i < info->s->base.fields ; i++)
    {
      enum en_fieldtype type;
      count[i].field_length=info->s->rec[i].length;
      type= count[i].field_type= (enum en_fieldtype) info->s->rec[i].type;
      if (type == FIELD_INTERVALL ||
	  type == FIELD_CONSTANT ||
	  type == FIELD_ZERO)
	type = FIELD_NORMAL;
      if (count[i].field_length <= 8 &&
	  (type == FIELD_NORMAL ||
unknown's avatar
unknown committed
765
	   type == FIELD_SKIP_ZERO))
unknown's avatar
unknown committed
766
	count[i].max_zero_fill= count[i].field_length;
767 768 769 770 771 772
      /*
        For every column initialize a tree, which is used to detect distinct
        column values. 'int_tree' works together with 'tree_buff' and
        'tree_pos'. It's keys are implemented by pointers into 'tree_buff'.
        This is accomplished by '-1' as the element size.
      */
773 774
      init_tree(&count[i].int_tree,0,0,-1,(qsort_cmp2) compare_tree,0, NULL,
		NULL);
unknown's avatar
unknown committed
775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821
      if (records && type != FIELD_BLOB && type != FIELD_VARCHAR)
	count[i].tree_pos=count[i].tree_buff =
	  my_malloc(count[i].field_length > 1 ? tree_buff_length : 2,
		    MYF(MY_WME));
    }
  }
  return count;
}


	/* Free memory used by counts and trees */

static void free_counts_and_tree_and_queue(HUFF_TREE *huff_trees, uint trees,
					   HUFF_COUNTS *huff_counts,
					   uint fields)
{
  register uint i;

  if (huff_trees)
  {
    for (i=0 ; i < trees ; i++)
    {
      if (huff_trees[i].element_buffer)
	my_free((gptr) huff_trees[i].element_buffer,MYF(0));
      if (huff_trees[i].code)
	my_free((gptr) huff_trees[i].code,MYF(0));
    }
    my_free((gptr) huff_trees,MYF(0));
  }
  if (huff_counts)
  {
    for (i=0 ; i < fields ; i++)
    {
      if (huff_counts[i].tree_buff)
      {
	my_free((gptr) huff_counts[i].tree_buff,MYF(0));
	delete_tree(&huff_counts[i].int_tree);
      }
    }
    my_free((gptr) huff_counts,MYF(0));
  }
  delete_queue(&queue);		/* This is safe to free */
  return;
}

	/* Read through old file and gather some statistics */

unknown's avatar
unknown committed
822
static int get_statistic(PACK_MRG_INFO *mrg,HUFF_COUNTS *huff_counts)
unknown's avatar
unknown committed
823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843
{
  int error;
  uint length;
  ulong reclength,max_blob_length;
  byte *record,*pos,*next_pos,*end_pos,*start_pos;
  ha_rows record_count;
  my_bool static_row_size;
  HUFF_COUNTS *count,*end_count;
  TREE_ELEMENT *element;
  DBUG_ENTER("get_statistic");

  reclength=mrg->file[0]->s->base.reclength;
  record=(byte*) my_alloca(reclength);
  end_count=huff_counts+mrg->file[0]->s->base.fields;
  record_count=0; glob_crc=0;
  max_blob_length=0;

  /* Check how to calculate checksum */
  static_row_size=1;
  for (count=huff_counts ; count < end_count ; count++)
  {
844 845
    if (count->field_type == FIELD_BLOB ||
        count->field_type == FIELD_VARCHAR)
unknown's avatar
unknown committed
846 847 848 849 850 851 852 853 854 855 856 857
    {
      static_row_size=0;
      break;
    }
  }

  mrg_reset(mrg);
  while ((error=mrg_rrnd(mrg,record)) != HA_ERR_END_OF_FILE)
  {
    ulong tot_blob_length=0;
    if (! error)
    {
858
      /* glob_crc is a checksum over all bytes of all records. */
unknown's avatar
unknown committed
859 860 861 862
      if (static_row_size)
	glob_crc+=mi_static_checksum(mrg->file[0],record);
      else
	glob_crc+=mi_checksum(mrg->file[0],record);
863 864

      /* Count the incidence of values separately for every column. */
unknown's avatar
unknown committed
865 866 867 868 869 870 871
      for (pos=record,count=huff_counts ;
	   count < end_count ;
	   count++,
	   pos=next_pos)
      {
	next_pos=end_pos=(start_pos=pos)+count->field_length;

872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904
	/*
          Put the whole column value in a tree if there is room for it.
          'int_tree' is used to quickly check for duplicate values.
          'tree_buff' collects as many distinct column values as
          possible. If the field length is > 1, it is tree_buff_length,
          else 2 bytes. Each value is 'field_length' bytes big. If there
          are more distinct column values than fit into the buffer, we
          give up with this tree. BLOBs and VARCHARs do not have a
          tree_buff as it can only be used with fixed length columns.
          For the special case of field length == 1, we handle only the
          case that there is only one distinct value in the table(s).
          Otherwise, we can have a maximum of 256 distinct values. This
          is then handled by the normal Huffman tree build.

          Another limit for collecting distinct column values is the
          number of values itself. Since we would need to build a
          Huffman tree for the values, we are limited by the 'IS_OFFSET'
          constant. This constant expresses a bit which is used to
          determine if a tree element holds a final value or an offset
          to a child element. Hence, all values and offsets need to be
          smaller than 'IS_OFFSET'. A tree element is implemented with
          two integer values, one for the left branch and one for the
          right branch. For the extreme case that the first element
          points to the last element, the number of integers in the tree
          must be less or equal to IS_OFFSET. So the number of elements
          must be less or equal to IS_OFFSET / 2.

          WARNING: At first, we insert a pointer into the record buffer
          as the key for the tree. If we got a new distinct value, which
          is really inserted into the tree, instead of being counted
          only, we will copy the column value from the record buffer to
          'tree_buff' and adjust the key pointer of the tree accordingly.
        */
unknown's avatar
unknown committed
905 906 907
	if (count->tree_buff)
	{
	  global_count=count;
908 909
	  if (!(element=tree_insert(&count->int_tree,pos, 0, 
				    count->int_tree.custom_arg)) ||
unknown's avatar
unknown committed
910
	      (element->count == 1 &&
911 912 913
	       (count->tree_buff + tree_buff_length <
                count->tree_pos + count->field_length)) ||
              (count->int_tree.elements_in_tree > IS_OFFSET / 2) ||
unknown's avatar
unknown committed
914 915 916 917 918 919 920 921 922
	      (count->field_length == 1 &&
	       count->int_tree.elements_in_tree > 1))
	  {
	    delete_tree(&count->int_tree);
	    my_free(count->tree_buff,MYF(0));
	    count->tree_buff=0;
	  }
	  else
	  {
923 924 925 926
            /*
              If tree_insert() succeeds, it either creates a new element
              or increments the counter of an existing element.
            */
unknown's avatar
unknown committed
927
	    if (element->count == 1)
928 929
	    {
              /* Copy the new column value into 'tree_buff'. */
unknown's avatar
unknown committed
930
	      memcpy(count->tree_pos,pos,(size_t) count->field_length);
931
              /* Adjust the key pointer in the tree. */
unknown's avatar
unknown committed
932
	      tree_set_pointer(element,count->tree_pos);
933
              /* Point behind the last column value so far. */
unknown's avatar
unknown committed
934 935 936 937 938 939 940
	      count->tree_pos+=count->field_length;
	    }
	  }
	}

	/* Save character counters and space-counts and zero-field-counts */
	if (count->field_type == FIELD_NORMAL ||
unknown's avatar
unknown committed
941
	    count->field_type == FIELD_SKIP_ENDSPACE)
unknown's avatar
unknown committed
942
	{
943
          /* Ignore trailing space. */
unknown's avatar
unknown committed
944 945 946
	  for ( ; end_pos > pos ; end_pos--)
	    if (end_pos[-1] != ' ')
	      break;
947
          /* Empty fields are just counted. Go to the next record. */
unknown's avatar
unknown committed
948 949 950 951 952 953
	  if (end_pos == pos)
	  {
	    count->empty_fields++;
	    count->max_zero_fill=0;
	    continue;
	  }
954 955 956 957
          /*
            Count the total of all trailing spaces and the number of
            short trailing spaces. Remember the longest trailing space.
          */
unknown's avatar
unknown committed
958 959 960 961 962 963 964
	  length= (uint) (next_pos-end_pos);
	  count->tot_end_space+=length;
	  if (length < 8)
	    count->end_space[length]++;
	  if (count->max_end_space < length)
	    count->max_end_space = length;
	}
965

unknown's avatar
unknown committed
966
	if (count->field_type == FIELD_NORMAL ||
unknown's avatar
unknown committed
967
	    count->field_type == FIELD_SKIP_PRESPACE)
unknown's avatar
unknown committed
968
	{
969
          /* Ignore leading space. */
unknown's avatar
unknown committed
970 971 972
	  for (pos=start_pos; pos < end_pos ; pos++)
	    if (pos[0] != ' ')
	      break;
973
          /* Empty fields are just counted. Go to the next record. */
unknown's avatar
unknown committed
974 975 976 977 978 979
	  if (end_pos == pos)
	  {
	    count->empty_fields++;
	    count->max_zero_fill=0;
	    continue;
	  }
980 981 982 983
          /*
            Count the total of all leading spaces and the number of
            short leading spaces. Remember the longest leading space.
          */
unknown's avatar
unknown committed
984 985 986 987 988 989 990
	  length= (uint) (pos-start_pos);
	  count->tot_pre_space+=length;
	  if (length < 8)
	    count->pre_space[length]++;
	  if (count->max_pre_space < length)
	    count->max_pre_space = length;
	}
991 992

        /* Calculate pos, end_pos, and max_length for variable length fields. */
unknown's avatar
unknown committed
993 994 995 996 997 998 999 1000 1001 1002 1003
	if (count->field_type == FIELD_BLOB)
	{
	  uint field_length=count->field_length -mi_portable_sizeof_char_ptr;
	  ulong blob_length= _mi_calc_blob_length(field_length, start_pos);
	  memcpy_fixed((char*) &pos,  start_pos+field_length,sizeof(char*));
	  end_pos=pos+blob_length;
	  tot_blob_length+=blob_length;
	  set_if_bigger(count->max_length,blob_length);
	}
	else if (count->field_type == FIELD_VARCHAR)
	{
1004 1005 1006 1007 1008
          uint pack_length= HA_VARCHAR_PACKLENGTH(count->field_length-1);
	  length= (pack_length == 1 ? (uint) *(uchar*) start_pos :
                   uint2korr(start_pos));
	  pos= start_pos+pack_length;
	  end_pos= pos+length;
unknown's avatar
unknown committed
1009 1010
	  set_if_bigger(count->max_length,length);
	}
1011 1012

        /* Evaluate 'max_zero_fill' for short fields. */
unknown's avatar
unknown committed
1013 1014
	if (count->field_length <= 8 &&
	    (count->field_type == FIELD_NORMAL ||
unknown's avatar
unknown committed
1015
	     count->field_type == FIELD_SKIP_ZERO))
unknown's avatar
unknown committed
1016 1017
	{
	  uint i;
1018
          /* Zero fields are just counted. Go to the next record. */
unknown's avatar
unknown committed
1019 1020 1021 1022 1023
	  if (!memcmp((byte*) start_pos,zero_string,count->field_length))
	  {
	    count->zero_fields++;
	    continue;
	  }
1024 1025 1026 1027 1028 1029
          /*
            max_zero_fill starts with field_length. It is decreased every
            time a shorter "zero trailer" is found. It is set to zero when
            an empty field is found (see above). This suggests that the
            variable should be called 'min_zero_fill'.
          */
unknown's avatar
unknown committed
1030 1031 1032 1033 1034
	  for (i =0 ; i < count->max_zero_fill && ! end_pos[-1 - (int) i] ;
	       i++) ;
	  if (i < count->max_zero_fill)
	    count->max_zero_fill=i;
	}
1035 1036

        /* Ignore zero fields and check fields. */
unknown's avatar
unknown committed
1037 1038 1039
	if (count->field_type == FIELD_ZERO ||
	    count->field_type == FIELD_CHECK)
	  continue;
1040 1041 1042 1043 1044

        /*
          Count the incidence of every byte value in the
          significant field value.
        */
unknown's avatar
unknown committed
1045 1046
	for ( ; pos < end_pos ; pos++)
	  count->counts[(uchar) *pos]++;
1047 1048

        /* Step to next field. */
unknown's avatar
unknown committed
1049
      }
1050

unknown's avatar
unknown committed
1051 1052 1053 1054 1055
      if (tot_blob_length > max_blob_length)
	max_blob_length=tot_blob_length;
      record_count++;
      if (write_loop && record_count % WRITE_COUNT == 0)
      {
1056 1057
	VOID(printf("%lu\r", (ulong) record_count));
        VOID(fflush(stdout));
unknown's avatar
unknown committed
1058 1059 1060 1061
      }
    }
    else if (error != HA_ERR_RECORD_DELETED)
    {
1062
      VOID(fprintf(stderr, "Got error %d while reading rows", error));
unknown's avatar
unknown committed
1063 1064
      break;
    }
1065 1066

    /* Step to next record. */
unknown's avatar
unknown committed
1067 1068 1069
  }
  if (write_loop)
  {
1070 1071
    VOID(printf("            \r"));
    VOID(fflush(stdout));
unknown's avatar
unknown committed
1072
  }
1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125

  /*
    If --debug=d,fakebigcodes is set, fake the counts to get big Huffman
    codes.
  */
  DBUG_EXECUTE_IF("fakebigcodes", fakebigcodes(huff_counts, end_count););

  DBUG_PRINT("info", ("Found the following number of incidents "
                      "of the byte codes:"));
  if (verbose >= 2)
    VOID(printf("Found the following number of incidents "
                "of the byte codes:\n"));
  for (count= huff_counts ; count < end_count; count++)
  {
    uint      idx;
    my_off_t  total_count;
    char      llbuf[32];

    DBUG_PRINT("info", ("column: %3u", count - huff_counts + 1));
    if (verbose >= 2)
      VOID(printf("column: %3u\n", count - huff_counts + 1));
    if (count->tree_buff)
    {
      DBUG_PRINT("info", ("number of distinct values: %u",
                          (count->tree_pos - count->tree_buff) /
                          count->field_length));
      if (verbose >= 2)
        VOID(printf("number of distinct values: %u\n",
                    (count->tree_pos - count->tree_buff) /
                    count->field_length));
    }
    total_count= 0;
    for (idx= 0; idx < 256; idx++)
    {
      if (count->counts[idx])
      {
        total_count+= count->counts[idx];
        DBUG_PRINT("info", ("counts[0x%02x]: %12s", idx,
                            llstr((longlong) count->counts[idx], llbuf)));
        if (verbose >= 2)
          VOID(printf("counts[0x%02x]: %12s\n", idx,
                      llstr((longlong) count->counts[idx], llbuf)));
      }
    }
    DBUG_PRINT("info", ("total:        %12s", llstr((longlong) total_count,
                                                    llbuf)));
    if ((verbose >= 2) && total_count)
    {
      VOID(printf("total:        %12s\n",
                  llstr((longlong) total_count, llbuf)));
    }
  }

unknown's avatar
unknown committed
1126 1127 1128 1129 1130 1131
  mrg->records=record_count;
  mrg->max_blob_length=max_blob_length;
  my_afree((gptr) record);
  DBUG_RETURN(error != HA_ERR_END_OF_FILE);
}

unknown's avatar
unknown committed
1132
static int compare_huff_elements(void *not_used __attribute__((unused)),
unknown's avatar
unknown committed
1133
				 byte *a, byte *b)
unknown's avatar
unknown committed
1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173
{
  return *((my_off_t*) a) < *((my_off_t*) b) ? -1 :
    (*((my_off_t*) a) == *((my_off_t*) b)  ? 0 : 1);
}

	/* Check each tree if we should use pre-space-compress, end-space-
	   compress, empty-field-compress or zero-field-compress */

static void check_counts(HUFF_COUNTS *huff_counts, uint trees,
			 my_off_t records)
{
  uint space_fields,fill_zero_fields,field_count[(int) FIELD_VARCHAR+1];
  my_off_t old_length,new_length,length;
  DBUG_ENTER("check_counts");

  bzero((gptr) field_count,sizeof(field_count));
  space_fields=fill_zero_fields=0;

  for (; trees-- ; huff_counts++)
  {
    if (huff_counts->field_type == FIELD_BLOB)
    {
      huff_counts->length_bits=max_bit(huff_counts->max_length);
      goto found_pack;
    }
    else if (huff_counts->field_type == FIELD_VARCHAR)
    {
      huff_counts->length_bits=max_bit(huff_counts->max_length);
      goto found_pack;
    }
    else if (huff_counts->field_type == FIELD_CHECK)
    {
      huff_counts->bytes_packed=0;
      huff_counts->counts[0]=0;
      goto found_pack;
    }

    huff_counts->field_type=FIELD_NORMAL;
    huff_counts->pack_type=0;

1174
    /* Check for zero-filled records (in this column), or zero records. */
unknown's avatar
unknown committed
1175 1176 1177
    if (huff_counts->zero_fields || ! records)
    {
      my_off_t old_space_count;
1178 1179 1180 1181
      /*
        If there are only zero filled records (in this column),
        or no records at all, we are done.
      */
unknown's avatar
unknown committed
1182 1183 1184 1185 1186 1187 1188
      if (huff_counts->zero_fields == records)
      {
	huff_counts->field_type= FIELD_ZERO;
	huff_counts->bytes_packed=0;
	huff_counts->counts[0]=0;
	goto found_pack;
      }
1189
      /* Remeber the number of significant spaces. */
unknown's avatar
unknown committed
1190
      old_space_count=huff_counts->counts[' '];
1191 1192 1193 1194 1195 1196
      /* Add all leading and trailing spaces. */
      huff_counts->counts[' ']+= (huff_counts->tot_end_space +
                                  huff_counts->tot_pre_space +
                                  huff_counts->empty_fields *
                                  huff_counts->field_length);
      /* Check, what the compressed length of this would be. */
unknown's avatar
unknown committed
1197
      old_length=calc_packed_length(huff_counts,0)+records/8;
1198
      /* Get the number of zero bytes. */
unknown's avatar
unknown committed
1199
      length=huff_counts->zero_fields*huff_counts->field_length;
1200
      /* Add it to the counts. */
unknown's avatar
unknown committed
1201
      huff_counts->counts[0]+=length;
1202
      /* Check, what the compressed length of this would be. */
unknown's avatar
unknown committed
1203
      new_length=calc_packed_length(huff_counts,0);
1204
      /* If the compression without the zeroes would be shorter, we are done. */
unknown's avatar
unknown committed
1205 1206
      if (old_length < new_length && huff_counts->field_length > 1)
      {
unknown's avatar
unknown committed
1207
	huff_counts->field_type=FIELD_SKIP_ZERO;
unknown's avatar
unknown committed
1208 1209 1210 1211
	huff_counts->counts[0]-=length;
	huff_counts->bytes_packed=old_length- records/8;
	goto found_pack;
      }
1212
      /* Remove the insignificant spaces, but keep the zeroes. */
unknown's avatar
unknown committed
1213 1214
      huff_counts->counts[' ']=old_space_count;
    }
1215
    /* Check, what the compressed length of this column would be. */
unknown's avatar
unknown committed
1216
    huff_counts->bytes_packed=calc_packed_length(huff_counts,0);
1217 1218 1219 1220 1221

    /*
      If there are enough empty records (in this column),
      treating them specially may pay off.
    */
unknown's avatar
unknown committed
1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242
    if (huff_counts->empty_fields)
    {
      if (huff_counts->field_length > 2 &&
	  huff_counts->empty_fields + (records - huff_counts->empty_fields)*
	  (1+max_bit(max(huff_counts->max_pre_space,
			 huff_counts->max_end_space))) <
	  records * max_bit(huff_counts->field_length))
      {
	huff_counts->pack_type |= PACK_TYPE_SPACE_FIELDS;
      }
      else
      {
	length=huff_counts->empty_fields*huff_counts->field_length;
	if (huff_counts->tot_end_space || ! huff_counts->tot_pre_space)
	{
	  huff_counts->tot_end_space+=length;
	  huff_counts->max_end_space=huff_counts->field_length;
	  if (huff_counts->field_length < 8)
	    huff_counts->end_space[huff_counts->field_length]+=
	      huff_counts->empty_fields;
	}
unknown's avatar
unknown committed
1243
	if (huff_counts->tot_pre_space)
unknown's avatar
unknown committed
1244 1245 1246 1247 1248 1249 1250 1251 1252
	{
	  huff_counts->tot_pre_space+=length;
	  huff_counts->max_pre_space=huff_counts->field_length;
	  if (huff_counts->field_length < 8)
	    huff_counts->pre_space[huff_counts->field_length]+=
	      huff_counts->empty_fields;
	}
      }
    }
1253 1254 1255 1256 1257

    /*
      If there are enough trailing spaces (in this column),
      treating them specially may pay off.
    */
unknown's avatar
unknown committed
1258 1259 1260 1261 1262
    if (huff_counts->tot_end_space)
    {
      huff_counts->counts[' ']+=huff_counts->tot_pre_space;
      if (test_space_compress(huff_counts,records,huff_counts->max_end_space,
			      huff_counts->end_space,
unknown's avatar
unknown committed
1263
			      huff_counts->tot_end_space,FIELD_SKIP_ENDSPACE))
unknown's avatar
unknown committed
1264 1265 1266
	goto found_pack;
      huff_counts->counts[' ']-=huff_counts->tot_pre_space;
    }
1267 1268 1269 1270 1271

    /*
      If there are enough leading spaces (in this column),
      treating them specially may pay off.
    */
unknown's avatar
unknown committed
1272 1273 1274 1275
    if (huff_counts->tot_pre_space)
    {
      if (test_space_compress(huff_counts,records,huff_counts->max_pre_space,
			      huff_counts->pre_space,
unknown's avatar
unknown committed
1276
			      huff_counts->tot_pre_space,FIELD_SKIP_PRESPACE))
unknown's avatar
unknown committed
1277 1278 1279 1280 1281 1282 1283 1284 1285
	goto found_pack;
    }

  found_pack:			/* Found field-packing */

    /* Test if we can use zero-fill */

    if (huff_counts->max_zero_fill &&
	(huff_counts->field_type == FIELD_NORMAL ||
unknown's avatar
unknown committed
1286
	 huff_counts->field_type == FIELD_SKIP_ZERO))
unknown's avatar
unknown committed
1287 1288
    {
      huff_counts->counts[0]-=huff_counts->max_zero_fill*
unknown's avatar
unknown committed
1289
	(huff_counts->field_type == FIELD_SKIP_ZERO ?
unknown's avatar
unknown committed
1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300
	 records - huff_counts->zero_fields : records);
      huff_counts->pack_type|=PACK_TYPE_ZERO_FILL;
      huff_counts->bytes_packed=calc_packed_length(huff_counts,0);
    }

    /* Test if intervall-field is better */

    if (huff_counts->tree_buff)
    {
      HUFF_TREE tree;

1301 1302
      DBUG_EXECUTE_IF("forceintervall",
                      huff_counts->bytes_packed= ~ (my_off_t) 0;);
unknown's avatar
unknown committed
1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327
      tree.element_buffer=0;
      if (!make_huff_tree(&tree,huff_counts) &&
	  tree.bytes_packed+tree.tree_pack_length < huff_counts->bytes_packed)
      {
	if (tree.elements == 1)
	  huff_counts->field_type=FIELD_CONSTANT;
	else
	  huff_counts->field_type=FIELD_INTERVALL;
	huff_counts->pack_type=0;
      }
      else
      {
	my_free((gptr) huff_counts->tree_buff,MYF(0));
	delete_tree(&huff_counts->int_tree);
	huff_counts->tree_buff=0;
      }
      if (tree.element_buffer)
	my_free((gptr) tree.element_buffer,MYF(0));
    }
    if (huff_counts->pack_type & PACK_TYPE_SPACE_FIELDS)
      space_fields++;
    if (huff_counts->pack_type & PACK_TYPE_ZERO_FILL)
      fill_zero_fields++;
    field_count[huff_counts->field_type]++;
  }
1328 1329 1330 1331 1332 1333 1334 1335 1336 1337
  DBUG_PRINT("info", ("normal:    %3d  empty-space:     %3d  "
                      "empty-zero:       %3d  empty-fill: %3d",
                      field_count[FIELD_NORMAL],space_fields,
                      field_count[FIELD_SKIP_ZERO],fill_zero_fields));
  DBUG_PRINT("info", ("pre-space: %3d  end-space:       %3d  "
                      "intervall-fields: %3d  zero:       %3d",
                      field_count[FIELD_SKIP_PRESPACE],
                      field_count[FIELD_SKIP_ENDSPACE],
                      field_count[FIELD_INTERVALL],
                      field_count[FIELD_ZERO]));
unknown's avatar
unknown committed
1338
  if (verbose)
1339 1340 1341 1342 1343 1344 1345 1346 1347 1348
    VOID(printf("\nnormal:    %3d  empty-space:     %3d  "
                "empty-zero:       %3d  empty-fill: %3d\n"
                "pre-space: %3d  end-space:       %3d  "
                "intervall-fields: %3d  zero:       %3d\n",
                field_count[FIELD_NORMAL],space_fields,
                field_count[FIELD_SKIP_ZERO],fill_zero_fields,
                field_count[FIELD_SKIP_PRESPACE],
                field_count[FIELD_SKIP_ENDSPACE],
                field_count[FIELD_INTERVALL],
                field_count[FIELD_ZERO]));
unknown's avatar
unknown committed
1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360
  DBUG_VOID_RETURN;
}

	/* Test if we can use space-compression and empty-field-compression */

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)
{
  int min_pos;
  uint length_bits,i;
1361
  my_off_t space_count,min_space_count,min_pack,new_length,skip;
unknown's avatar
unknown committed
1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380

  length_bits=max_bit(max_space_length);

		/* Default no end_space-packing */
  space_count=huff_counts->counts[(uint) ' '];
  min_space_count= (huff_counts->counts[(uint) ' ']+= tot_space_count);
  min_pack=calc_packed_length(huff_counts,0);
  min_pos= -2;
  huff_counts->counts[(uint) ' ']=space_count;

	/* Test with allways space-count */
  new_length=huff_counts->bytes_packed+length_bits*records/8;
  if (new_length+1 < min_pack)
  {
    min_pos= -1;
    min_pack=new_length;
    min_space_count=space_count;
  }
	/* Test with length-flag */
1381
  for (skip=0L, i=0 ; i < 8 ; i++)
unknown's avatar
unknown committed
1382 1383 1384 1385 1386
  {
    if (space_counts[i])
    {
      if (i)
	huff_counts->counts[(uint) ' ']+=space_counts[i];
1387
      skip+=huff_counts->pre_space[i];
unknown's avatar
unknown committed
1388
      new_length=calc_packed_length(huff_counts,0)+
1389
	(records+(records-skip)*(1+length_bits))/8;
unknown's avatar
unknown committed
1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444
      if (new_length < min_pack)
      {
	min_pos=(int) i;
	min_pack=new_length;
	min_space_count=huff_counts->counts[(uint) ' '];
      }
    }
  }

  huff_counts->counts[(uint) ' ']=min_space_count;
  huff_counts->bytes_packed=min_pack;
  switch (min_pos) {
  case -2:
    return(0);				/* No space-compress */
  case -1:				/* Always space-count */
    huff_counts->field_type=field_type;
    huff_counts->min_space=0;
    huff_counts->length_bits=max_bit(max_space_length);
    break;
  default:
    huff_counts->field_type=field_type;
    huff_counts->min_space=(uint) min_pos;
    huff_counts->pack_type|=PACK_TYPE_SELECTED;
    huff_counts->length_bits=max_bit(max_space_length);
    break;
  }
  return(1);				/* Using space-compress */
}


	/* Make a huff_tree of each huff_count */

static HUFF_TREE* make_huff_trees(HUFF_COUNTS *huff_counts, uint trees)
{
  uint tree;
  HUFF_TREE *huff_tree;
  DBUG_ENTER("make_huff_trees");

  if (!(huff_tree=(HUFF_TREE*) my_malloc(trees*sizeof(HUFF_TREE),
					 MYF(MY_WME | MY_ZEROFILL))))
    DBUG_RETURN(0);

  for (tree=0 ; tree < trees ; tree++)
  {
    if (make_huff_tree(huff_tree+tree,huff_counts+tree))
    {
      while (tree--)
	my_free((gptr) huff_tree[tree].element_buffer,MYF(0));
      my_free((gptr) huff_tree,MYF(0));
      DBUG_RETURN(0);
    }
  }
  DBUG_RETURN(huff_tree);
}

1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462
/*
  Build a Huffman tree.

  SYNOPSIS
    make_huff_tree()
    huff_tree                   The Huffman tree.
    huff_counts                 The counts.

  DESCRIPTION
    Build a Huffman tree according to huff_counts->counts or
    huff_counts->tree_buff. tree_buff, if non-NULL contains up to
    tree_buff_length of distinct column values. In that case, whole
    values can be Huffman encoded instead of single bytes.

  RETURN
    0           OK
    != 0        Error
*/
unknown's avatar
unknown committed
1463 1464 1465 1466 1467

static int make_huff_tree(HUFF_TREE *huff_tree, HUFF_COUNTS *huff_counts)
{
  uint i,found,bits_packed,first,last;
  my_off_t bytes_packed;
unknown's avatar
unknown committed
1468
  HUFF_ELEMENT *a,*b,*new_huff_el;
unknown's avatar
unknown committed
1469 1470 1471 1472

  first=last=0;
  if (huff_counts->tree_buff)
  {
1473
    /* Calculate the number of distinct values in tree_buff. */
unknown's avatar
unknown committed
1474 1475 1476 1477 1478 1479
    found= (uint) (huff_counts->tree_pos - huff_counts->tree_buff) /
      huff_counts->field_length;
    first=0; last=found-1;
  }
  else
  {
1480
    /* Count the number of byte codes found in the column. */
unknown's avatar
unknown committed
1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493
    for (i=found=0 ; i < 256 ; i++)
    {
      if (huff_counts->counts[i])
      {
	if (! found++)
	  first=i;
	last=i;
      }
    }
    if (found < 2)
      found=2;
  }

1494
  /* When using 'tree_buff' we can have more that 256 values. */
unknown's avatar
unknown committed
1495 1496 1497 1498 1499 1500 1501
  if (queue.max_elements < found)
  {
    delete_queue(&queue);
    if (init_queue(&queue,found,0,0,compare_huff_elements,0))
      return -1;
  }

1502
  /* Allocate or reallocate an element buffer for the Huffman tree. */
unknown's avatar
unknown committed
1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535
  if (!huff_tree->element_buffer)
  {
    if (!(huff_tree->element_buffer=
	 (HUFF_ELEMENT*) my_malloc(found*2*sizeof(HUFF_ELEMENT),MYF(MY_WME))))
      return 1;
  }
  else
  {
    HUFF_ELEMENT *temp;
    if (!(temp=
	  (HUFF_ELEMENT*) my_realloc((gptr) huff_tree->element_buffer,
				     found*2*sizeof(HUFF_ELEMENT),
				     MYF(MY_WME))))
      return 1;
    huff_tree->element_buffer=temp;
  }

  huff_counts->tree=huff_tree;
  huff_tree->counts=huff_counts;
  huff_tree->min_chr=first;
  huff_tree->max_chr=last;
  huff_tree->char_bits=max_bit(last-first);
  huff_tree->offset_bits=max_bit(found-1)+1;

  if (huff_counts->tree_buff)
  {
    huff_tree->elements=0;
    huff_tree->tree_pack_length=(1+15+16+5+5+
				 (huff_tree->char_bits+1)*found+
				 (huff_tree->offset_bits+1)*
				 (found-2)+7)/8 +
				   (uint) (huff_tree->counts->tree_pos-
					   huff_tree->counts->tree_buff);
1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548
    /*
      Put a HUFF_ELEMENT into the queue for every distinct column value.

      tree_walk() calls save_counts_in_queue() for every element in
      'int_tree'. This takes elements from the target trees element
      buffer and places references to them into the buffer of the
      priority queue. We insert in column value order, but the order is
      in fact irrelevant here. We will establish the correct order
      later.
    */
    tree_walk(&huff_counts->int_tree,
	      (int (*)(void*, element_count,void*)) save_counts_in_queue,
	      (gptr) huff_tree, left_root_right);
unknown's avatar
unknown committed
1549 1550 1551 1552 1553 1554 1555 1556
  }
  else
  {
    huff_tree->elements=found;
    huff_tree->tree_pack_length=(9+9+5+5+
				 (huff_tree->char_bits+1)*found+
				 (huff_tree->offset_bits+1)*
				 (found-2)+7)/8;
1557 1558
    /*
      Put a HUFF_ELEMENT into the queue for every byte code found in the column.
unknown's avatar
unknown committed
1559

1560 1561 1562 1563 1564 1565
      The elements are taken from the target trees element buffer.
      Instead of using queue_insert(), we just place references to the
      elements into the buffer of the priority queue. We insert in byte
      value order, but the order is in fact irrelevant here. We will
      establish the correct order later.
    */
unknown's avatar
unknown committed
1566 1567 1568 1569
    for (i=first, found=0 ; i <= last ; i++)
    {
      if (huff_counts->counts[i])
      {
unknown's avatar
unknown committed
1570 1571 1572 1573 1574
	new_huff_el=huff_tree->element_buffer+(found++);
	new_huff_el->count=huff_counts->counts[i];
	new_huff_el->a.leaf.null=0;
	new_huff_el->a.leaf.element_nr=i;
	queue.root[found]=(byte*) new_huff_el;
unknown's avatar
unknown committed
1575 1576
      }
    }
1577 1578 1579 1580 1581
    /*
      If there is only a single byte value in this field in all records,
      add a second element with zero incidence. This is required to enter
      the loop, which builds the Huffman tree.
    */
unknown's avatar
unknown committed
1582
    while (found < 2)
1583
    {
unknown's avatar
unknown committed
1584 1585 1586
      new_huff_el=huff_tree->element_buffer+(found++);
      new_huff_el->count=0;
      new_huff_el->a.leaf.null=0;
unknown's avatar
unknown committed
1587
      if (last)
unknown's avatar
unknown committed
1588
	new_huff_el->a.leaf.element_nr=huff_tree->min_chr=last-1;
unknown's avatar
unknown committed
1589
      else
unknown's avatar
unknown committed
1590 1591
	new_huff_el->a.leaf.element_nr=huff_tree->max_chr=last+1;
      queue.root[found]=(byte*) new_huff_el;
unknown's avatar
unknown committed
1592 1593
    }
  }
1594 1595

  /* Make a queue from the queue buffer. */
unknown's avatar
unknown committed
1596 1597
  queue.elements=found;

1598 1599 1600 1601
  /*
    Make a priority queue from the queue. Construct its index so that we
    have a partially ordered tree.
  */
unknown's avatar
unknown committed
1602 1603
  for (i=found/2 ; i > 0 ; i--)
    _downheap(&queue,i);
1604 1605

  /* The Huffman algorithm. */
unknown's avatar
unknown committed
1606 1607 1608
  bytes_packed=0; bits_packed=0;
  for (i=1 ; i < found ; i++)
  {
1609 1610 1611 1612 1613
    /*
      Pop the top element from the queue (the one with the least incidence).
      Popping from a priority queue includes a re-ordering of the queue,
      to get the next least incidence element to the top.
    */
unknown's avatar
unknown committed
1614
    a=(HUFF_ELEMENT*) queue_remove(&queue,0);
1615 1616 1617 1618
    /*
      Copy the next least incidence element. The queue implementation
      reserves root[0] for temporary purposes. root[1] is the top.
    */
unknown's avatar
unknown committed
1619
    b=(HUFF_ELEMENT*) queue.root[1];
1620
    /* Get a new element from the element buffer. */
unknown's avatar
unknown committed
1621
    new_huff_el=huff_tree->element_buffer+found+i;
1622
    /* The new element gets the sum of the two least incidence elements. */
unknown's avatar
unknown committed
1623
    new_huff_el->count=a->count+b->count;
1624 1625 1626 1627 1628 1629 1630 1631
    /*
      The Huffman algorithm assigns another bit to the code for a byte
      every time that bytes incidence is combined (directly or indirectly)
      to a new element as one of the two least incidence elements.
      This means that one more bit per incidence of that byte is required
      in the resulting file. So we add the new combined incidence as the
      number of bits by which the result grows.
    */
unknown's avatar
unknown committed
1632 1633
    bits_packed+=(uint) (new_huff_el->count & 7);
    bytes_packed+=new_huff_el->count/8;
1634 1635
    /* The new element points to its children, lesser in left.  */
    new_huff_el->a.nod.left=a;
unknown's avatar
unknown committed
1636
    new_huff_el->a.nod.right=b;
1637 1638 1639 1640
    /*
      Replace the copied top element by the new element and re-order the
      queue.
    */
unknown's avatar
unknown committed
1641
    queue.root[1]=(byte*) new_huff_el;
unknown's avatar
unknown committed
1642 1643 1644 1645 1646 1647 1648
    queue_replaced(&queue);
  }
  huff_tree->root=(HUFF_ELEMENT*) queue.root[1];
  huff_tree->bytes_packed=bytes_packed+(bits_packed+7)/8;
  return 0;
}

1649 1650
static int compare_tree(void* cmp_arg __attribute__((unused)),
			register const uchar *s, register const uchar *t)
unknown's avatar
unknown committed
1651 1652 1653 1654 1655 1656 1657 1658
{
  uint length;
  for (length=global_count->field_length; length-- ;)
    if (*s++ != *t++)
      return (int) s[-1] - (int) t[-1];
  return 0;
}

1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678
/*
  Organize distinct column values and their incidences into a priority queue.

  SYNOPSIS
    save_counts_in_queue()
    key                         The column value.
    count                       The incidence of this value.
    tree                        The Huffman tree to be built later.

  DESCRIPTION
    We use the element buffer of the targeted tree. The distinct column
    values are organized in a priority queue first. The Huffman
    algorithm will later organize the elements into a Huffman tree. For
    the time being, we just place references to the elements into the
    queue buffer. The buffer will later be organized into a priority
    queue.

  RETURN
    0
 */
unknown's avatar
unknown committed
1679 1680 1681 1682

static int save_counts_in_queue(byte *key, element_count count,
				HUFF_TREE *tree)
{
unknown's avatar
unknown committed
1683
  HUFF_ELEMENT *new_huff_el;
unknown's avatar
unknown committed
1684

unknown's avatar
unknown committed
1685 1686 1687 1688
  new_huff_el=tree->element_buffer+(tree->elements++);
  new_huff_el->count=count;
  new_huff_el->a.leaf.null=0;
  new_huff_el->a.leaf.element_nr= (uint) (key- tree->counts->tree_buff) /
unknown's avatar
unknown committed
1689
    tree->counts->field_length;
unknown's avatar
unknown committed
1690
  queue.root[tree->elements]=(byte*) new_huff_el;
unknown's avatar
unknown committed
1691 1692 1693 1694
  return 0;
}


1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711
/*
  Calculate length of file if given counts should be used.

  SYNOPSIS
    calc_packed_length()
    huff_counts                 The counts for a column of the table(s).
    add_tree_lenght             If the decode tree length should be added.

  DESCRIPTION
    We need to follow the Huffman algorithm until we know, how many bits
    are required for each byte code. But we do not need the resulting
    Huffman tree. Hence, we can leave out some steps which are essential
    in make_huff_tree().

  RETURN
    Number of bytes required to compress this table column.
*/
unknown's avatar
unknown committed
1712 1713 1714 1715 1716 1717 1718 1719 1720

static my_off_t calc_packed_length(HUFF_COUNTS *huff_counts,
				   uint add_tree_lenght)
{
  uint i,found,bits_packed,first,last;
  my_off_t bytes_packed;
  HUFF_ELEMENT element_buffer[256];
  DBUG_ENTER("calc_packed_length");

1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737
  /* 
    WARNING: We use a small hack for efficiency: Instead of placing
    references to HUFF_ELEMENTs into the queue, we just insert
    references to the counts of the byte codes which appeared in this
    table column. During the Huffman algorithm they are successively
    replaced by references to HUFF_ELEMENTs. This works, because
    HUFF_ELEMENTs have the incidence count at their beginning.
    Regardless, wether the queue array contains references to counts of
    type my_off_t or references to HUFF_ELEMENTs which have the count of
    type my_off_t at their beginning, it always points to a count of the
    same type.

    Instead of using queue_insert(), we just copy the references into
    the buffer of the priority queue. We insert in byte value order, but
    the order is in fact irrelevant here. We will establish the correct
    order later.
  */
unknown's avatar
unknown committed
1738 1739 1740 1741 1742 1743 1744 1745
  first=last=0;
  for (i=found=0 ; i < 256 ; i++)
  {
    if (huff_counts->counts[i])
    {
      if (! found++)
	first=i;
      last=i;
1746
      /* We start with root[1], which is the queues top element. */
unknown's avatar
unknown committed
1747 1748 1749 1750 1751
      queue.root[found]=(byte*) &huff_counts->counts[i];
    }
  }
  if (!found)
    DBUG_RETURN(0);			/* Empty tree */
1752 1753 1754 1755 1756
  /*
    If there is only a single byte value in this field in all records,
    add a second element with zero incidence. This is required to enter
    the loop, which follows the Huffman algorithm.
  */
unknown's avatar
unknown committed
1757 1758 1759
  if (found < 2)
    queue.root[++found]=(byte*) &huff_counts->counts[last ? 0 : 1];

1760
  /* Make a queue from the queue buffer. */
unknown's avatar
unknown committed
1761 1762 1763
  queue.elements=found;

  bytes_packed=0; bits_packed=0;
1764
  /* Add the length of the coding table, which would become part of the file. */
unknown's avatar
unknown committed
1765 1766 1767
  if (add_tree_lenght)
    bytes_packed=(8+9+5+5+(max_bit(last-first)+1)*found+
		  (max_bit(found-1)+1+1)*(found-2) +7)/8;
1768 1769 1770 1771 1772

  /*
    Make a priority queue from the queue. Construct its index so that we
    have a partially ordered tree.
  */
unknown's avatar
unknown committed
1773 1774
  for (i=(found+1)/2 ; i > 0 ; i--)
    _downheap(&queue,i);
1775 1776

  /* The Huffman algorithm. */
unknown's avatar
unknown committed
1777 1778
  for (i=0 ; i < found-1 ; i++)
  {
1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805
    my_off_t        *a;
    my_off_t        *b;
    HUFF_ELEMENT    *new_huff_el;

    /*
      Pop the top element from the queue (the one with the least
      incidence). Popping from a priority queue includes a re-ordering
      of the queue, to get the next least incidence element to the top.
    */
    a= (my_off_t*) queue_remove(&queue, 0);
    /*
      Copy the next least incidence element. The queue implementation
      reserves root[0] for temporary purposes. root[1] is the top.
    */
    b= (my_off_t*) queue.root[1];
    /* Create a new element in a local (automatic) buffer. */
    new_huff_el= element_buffer + i;
    /* The new element gets the sum of the two least incidence elements. */
    new_huff_el->count= *a + *b;
    /*
      The Huffman algorithm assigns another bit to the code for a byte
      every time that bytes incidence is combined (directly or indirectly)
      to a new element as one of the two least incidence elements.
      This means that one more bit per incidence of that byte is required
      in the resulting file. So we add the new combined incidence as the
      number of bits by which the result grows.
    */
unknown's avatar
unknown committed
1806 1807
    bits_packed+=(uint) (new_huff_el->count & 7);
    bytes_packed+=new_huff_el->count/8;
1808 1809 1810 1811 1812
    /*
      Replace the copied top element by the new element and re-order the
      queue. This successively replaces the references to counts by
      references to HUFF_ELEMENTs.
    */
unknown's avatar
unknown committed
1813
    queue.root[1]=(byte*) new_huff_el;
unknown's avatar
unknown committed
1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859
    queue_replaced(&queue);
  }
  DBUG_RETURN(bytes_packed+(bits_packed+7)/8);
}


	/* Remove trees that don't give any compression */

static uint join_same_trees(HUFF_COUNTS *huff_counts, uint trees)
{
  uint k,tree_number;
  HUFF_COUNTS count,*i,*j,*last_count;

  last_count=huff_counts+trees;
  for (tree_number=0, i=huff_counts ; i < last_count ; i++)
  {
    if (!i->tree->tree_number)
    {
      i->tree->tree_number= ++tree_number;
      if (i->tree_buff)
	continue;			/* Don't join intervall */
      for (j=i+1 ; j < last_count ; j++)
      {
	if (! j->tree->tree_number && ! j->tree_buff)
	{
	  for (k=0 ; k < 256 ; k++)
	    count.counts[k]=i->counts[k]+j->counts[k];
	  if (calc_packed_length(&count,1) <=
	      i->tree->bytes_packed + j->tree->bytes_packed+
	      i->tree->tree_pack_length+j->tree->tree_pack_length+
	      ALLOWED_JOIN_DIFF)
	  {
	    memcpy_fixed((byte*) i->counts,(byte*) count.counts,
			 sizeof(count.counts[0])*256);
	    my_free((gptr) j->tree->element_buffer,MYF(0));
	    j->tree->element_buffer=0;
	    j->tree=i->tree;
	    bmove((byte*) i->counts,(byte*) count.counts,
		  sizeof(count.counts[0])*256);
	    if (make_huff_tree(i->tree,i))
	      return (uint) -1;
	  }
	}
      }
    }
  }
1860 1861
  DBUG_PRINT("info", ("Original trees:  %d  After join: %d",
                      trees, tree_number));
unknown's avatar
unknown committed
1862
  if (verbose)
1863
    VOID(printf("Original trees:  %d  After join: %d\n", trees, tree_number));
unknown's avatar
unknown committed
1864 1865 1866 1867
  return tree_number;			/* Return trees left */
}


1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879
/*
  Fill in huff_tree encode tables.

  SYNOPSIS
    make_huff_decode_table()
    huff_tree               An array of HUFF_TREE which are to be encoded.
    trees                   The number of HUFF_TREE in the array.

  RETURN
    0           success
    != 0        error
*/
unknown's avatar
unknown committed
1880 1881 1882 1883 1884 1885 1886 1887 1888 1889

static int make_huff_decode_table(HUFF_TREE *huff_tree, uint trees)
{
  uint elements;
  for ( ; trees-- ; huff_tree++)
  {
    if (huff_tree->tree_number > 0)
    {
      elements=huff_tree->counts->tree_buff ? huff_tree->elements : 256;
      if (!(huff_tree->code =
1890 1891 1892
            (ulonglong*) my_malloc(elements*
                                   (sizeof(ulonglong) + sizeof(uchar)),
                                   MYF(MY_WME | MY_ZEROFILL))))
unknown's avatar
unknown committed
1893 1894
	return 1;
      huff_tree->code_len=(uchar*) (huff_tree->code+elements);
1895 1896
      make_traverse_code_tree(huff_tree, huff_tree->root,
                              8 * sizeof(ulonglong), LL(0));
unknown's avatar
unknown committed
1897 1898 1899 1900 1901 1902 1903 1904
    }
  }
  return 0;
}


static void make_traverse_code_tree(HUFF_TREE *huff_tree,
				    HUFF_ELEMENT *element,
1905
				    uint size, ulonglong code)
unknown's avatar
unknown committed
1906 1907 1908 1909 1910
{
  uint chr;
  if (!element->a.leaf.null)
  {
    chr=element->a.leaf.element_nr;
1911 1912 1913 1914
    huff_tree->code_len[chr]= (uchar) (8 * sizeof(ulonglong) - size);
    huff_tree->code[chr]= (code >> size);
    if (huff_tree->height < 8 * sizeof(ulonglong) - size)
        huff_tree->height= 8 * sizeof(ulonglong) - size;
unknown's avatar
unknown committed
1915 1916 1917 1918 1919
  }
  else
  {
    size--;
    make_traverse_code_tree(huff_tree,element->a.nod.left,size,code);
1920 1921
    make_traverse_code_tree(huff_tree, element->a.nod.right, size,
			    code + (((ulonglong) 1) << size));
unknown's avatar
unknown committed
1922 1923 1924 1925 1926
  }
  return;
}


1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988
/*
  Convert a value into binary digits.

  SYNOPSIS
    bindigits()
    value                       The value.
    length                      The number of low order bits to convert.

  NOTE
    The result string is in static storage. It is reused on every call.
    So you cannot use it twice in one expression.

  RETURN
    A pointer to a static NUL-terminated string.
 */

static char *bindigits(ulonglong value, uint bits)
{
  static char digits[72];
  char *ptr= digits;
  uint idx= bits;

  DBUG_ASSERT(idx < sizeof(digits));
  while (idx)
    *(ptr++)= '0' + ((value >> (--idx)) & 1);
  *ptr= '\0';
  return digits;
}


/*
  Convert a value into hexadecimal digits.

  SYNOPSIS
    hexdigits()
    value                       The value.

  NOTE
    The result string is in static storage. It is reused on every call.
    So you cannot use it twice in one expression.

  RETURN
    A pointer to a static NUL-terminated string.
 */

static char *hexdigits(ulonglong value)
{
  static char digits[20];
  char *ptr= digits;
  uint idx= 2 * sizeof(value); /* Two hex digits per byte. */

  DBUG_ASSERT(idx < sizeof(digits));
  while (idx)
  {
    if ((*(ptr++)= '0' + ((value >> (4 * (--idx))) & 0xf)) > '9')
      *(ptr - 1)+= 'a' - '9' - 1;
  }
  *ptr= '\0';
  return digits;
}


unknown's avatar
unknown committed
1989 1990
	/* Write header to new packed data file */

unknown's avatar
unknown committed
1991
static int write_header(PACK_MRG_INFO *mrg,uint head_length,uint trees,
unknown's avatar
unknown committed
1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021
			my_off_t tot_elements,my_off_t filelength)
{
  byte *buff=file_buffer.pos;

  bzero(buff,HEAD_LENGTH);
  memcpy_fixed(buff,myisam_pack_file_magic,4);
  int4store(buff+4,head_length);
  int4store(buff+8, mrg->min_pack_length);
  int4store(buff+12,mrg->max_pack_length);
  int4store(buff+16,tot_elements);
  int4store(buff+20,intervall_length);
  int2store(buff+24,trees);
  buff[26]=(char) mrg->ref_length;
	/* Save record pointer length */
  buff[27]= (uchar) mi_get_pointer_length((ulonglong) filelength,2);
  if (test_only)
    return 0;
  VOID(my_seek(file_buffer.file,0L,MY_SEEK_SET,MYF(0)));
  return my_write(file_buffer.file,file_buffer.pos,HEAD_LENGTH,
		  MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)) != 0;
}

	/* Write fieldinfo to new packed file */

static void write_field_info(HUFF_COUNTS *counts, uint fields, uint trees)
{
  reg1 uint i;
  uint huff_tree_bits;
  huff_tree_bits=max_bit(trees ? trees-1 : 0);

2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060
  DBUG_PRINT("info", (""));
  DBUG_PRINT("info", ("column types:"));
  DBUG_PRINT("info", ("FIELD_NORMAL          0"));
  DBUG_PRINT("info", ("FIELD_SKIP_ENDSPACE   1"));
  DBUG_PRINT("info", ("FIELD_SKIP_PRESPACE   2"));
  DBUG_PRINT("info", ("FIELD_SKIP_ZERO       3"));
  DBUG_PRINT("info", ("FIELD_BLOB            4"));
  DBUG_PRINT("info", ("FIELD_CONSTANT        5"));
  DBUG_PRINT("info", ("FIELD_INTERVALL       6"));
  DBUG_PRINT("info", ("FIELD_ZERO            7"));
  DBUG_PRINT("info", ("FIELD_VARCHAR         8"));
  DBUG_PRINT("info", ("FIELD_CHECK           9"));
  DBUG_PRINT("info", (""));
  DBUG_PRINT("info", ("pack type as a set of flags:"));
  DBUG_PRINT("info", ("PACK_TYPE_SELECTED      1"));
  DBUG_PRINT("info", ("PACK_TYPE_SPACE_FIELDS  2"));
  DBUG_PRINT("info", ("PACK_TYPE_ZERO_FILL     4"));
  DBUG_PRINT("info", (""));
  if (verbose >= 2)
  {
    VOID(printf("\n"));
    VOID(printf("column types:\n"));
    VOID(printf("FIELD_NORMAL          0\n"));
    VOID(printf("FIELD_SKIP_ENDSPACE   1\n"));
    VOID(printf("FIELD_SKIP_PRESPACE   2\n"));
    VOID(printf("FIELD_SKIP_ZERO       3\n"));
    VOID(printf("FIELD_BLOB            4\n"));
    VOID(printf("FIELD_CONSTANT        5\n"));
    VOID(printf("FIELD_INTERVALL       6\n"));
    VOID(printf("FIELD_ZERO            7\n"));
    VOID(printf("FIELD_VARCHAR         8\n"));
    VOID(printf("FIELD_CHECK           9\n"));
    VOID(printf("\n"));
    VOID(printf("pack type as a set of flags:\n"));
    VOID(printf("PACK_TYPE_SELECTED      1\n"));
    VOID(printf("PACK_TYPE_SPACE_FIELDS  2\n"));
    VOID(printf("PACK_TYPE_ZERO_FILL     4\n"));
    VOID(printf("\n"));
  }
unknown's avatar
unknown committed
2061 2062
  for (i=0 ; i++ < fields ; counts++)
  {
2063
    write_bits((ulonglong) (int) counts->field_type, 5);
unknown's avatar
unknown committed
2064 2065 2066 2067 2068
    write_bits(counts->pack_type,6);
    if (counts->pack_type & PACK_TYPE_ZERO_FILL)
      write_bits(counts->max_zero_fill,5);
    else
      write_bits(counts->length_bits,5);
2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079
    write_bits((ulonglong) counts->tree->tree_number - 1, huff_tree_bits);
    DBUG_PRINT("info", ("column: %3u  type: %2u  pack: %2u  zero: %4u  "
                        "lbits: %2u  tree: %2u  length: %4u",
                        i , counts->field_type, counts->pack_type,
                        counts->max_zero_fill, counts->length_bits,
                        counts->tree->tree_number, counts->field_length));
    if (verbose >= 2)
      VOID(printf("column: %3u  type: %2u  pack: %2u  zero: %4u  lbits: %2u  "
                  "tree: %2u  length: %4u\n", i , counts->field_type,
                  counts->pack_type, counts->max_zero_fill, counts->length_bits,
                  counts->tree->tree_number, counts->field_length));
unknown's avatar
unknown committed
2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091
  }
  flush_bits();
  return;
}

	/* Write all huff_trees to new datafile. Return tot count of
	   elements in all trees
	   Returns 0 on error */

static my_off_t write_huff_tree(HUFF_TREE *huff_tree, uint trees)
{
  uint i,int_length;
2092 2093 2094
  uint tree_no;
  uint codes;
  uint errors= 0;
unknown's avatar
unknown committed
2095 2096 2097
  uint *packed_tree,*offset,length;
  my_off_t elements;

2098
  /* Find the highest number of elements in the trees. */
unknown's avatar
unknown committed
2099 2100 2101
  for (i=length=0 ; i < trees ; i++)
    if (huff_tree[i].tree_number > 0 && huff_tree[i].elements > length)
      length=huff_tree[i].elements;
2102 2103 2104 2105
  /*
    Allocate a buffer for packing a decode tree. Two numbers per element
    (left child and right child).
  */
unknown's avatar
unknown committed
2106 2107 2108 2109 2110 2111
  if (!(packed_tree=(uint*) my_alloca(sizeof(uint)*length*2)))
  {
    my_error(EE_OUTOFMEMORY,MYF(ME_BELL),sizeof(uint)*length*2);
    return 0;
  }

2112 2113 2114 2115
  DBUG_PRINT("info", (""));
  if (verbose >= 2)
    VOID(printf("\n"));
  tree_no= 0;
unknown's avatar
unknown committed
2116 2117 2118
  intervall_length=0;
  for (elements=0; trees-- ; huff_tree++)
  {
2119
    /* Skip columns that have been joined with other columns. */
unknown's avatar
unknown committed
2120 2121
    if (huff_tree->tree_number == 0)
      continue;				/* Deleted tree */
2122 2123 2124 2125 2126
    tree_no++;
    DBUG_PRINT("info", (""));
    if (verbose >= 3)
      VOID(printf("\n"));
    /* Count the total number of elements (byte codes or column values). */
unknown's avatar
unknown committed
2127 2128
    elements+=huff_tree->elements;
    huff_tree->max_offset=2;
2129
    /* Build a tree of offsets and codes for decoding in 'packed_tree'. */
unknown's avatar
unknown committed
2130 2131 2132 2133
    if (huff_tree->elements <= 1)
      offset=packed_tree;
    else
      offset=make_offset_code_tree(huff_tree,huff_tree->root,packed_tree);
2134 2135

    /* This should be the same as 'length' above. */
unknown's avatar
unknown committed
2136
    huff_tree->offset_bits=max_bit(huff_tree->max_offset);
2137 2138 2139 2140 2141

    /*
      Since we check this during collecting the distinct column values,
      this should never happen.
    */
unknown's avatar
unknown committed
2142 2143
    if (huff_tree->max_offset >= IS_OFFSET)
    {				/* This should be impossible */
2144 2145
      VOID(fprintf(stderr, "Tree offset got too big: %d, aborted\n",
                   huff_tree->max_offset));
unknown's avatar
unknown committed
2146 2147 2148 2149
      my_afree((gptr) packed_tree);
      return 0;
    }

2150 2151 2152 2153 2154
    DBUG_PRINT("info", ("pos: %lu  elements: %u  tree-elements: %lu  "
                        "char_bits: %u\n",
                        (ulong) (file_buffer.pos - file_buffer.buffer),
                        huff_tree->elements, (ulong) (offset - packed_tree),
                        huff_tree->char_bits));
unknown's avatar
unknown committed
2155 2156
    if (!huff_tree->counts->tree_buff)
    {
2157
      /* We do a byte compression on this column. Mark with bit 0. */
unknown's avatar
unknown committed
2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168
      write_bits(0,1);
      write_bits(huff_tree->min_chr,8);
      write_bits(huff_tree->elements,9);
      write_bits(huff_tree->char_bits,5);
      write_bits(huff_tree->offset_bits,5);
      int_length=0;
    }
    else
    {
      int_length=(uint) (huff_tree->counts->tree_pos -
			 huff_tree->counts->tree_buff);
2169
      /* We have distinct column values for this column. Mark with bit 1. */
unknown's avatar
unknown committed
2170 2171 2172 2173 2174 2175 2176
      write_bits(1,1);
      write_bits(huff_tree->elements,15);
      write_bits(int_length,16);
      write_bits(huff_tree->char_bits,5);
      write_bits(huff_tree->offset_bits,5);
      intervall_length+=int_length;
    }
2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191
    DBUG_PRINT("info", ("tree: %2u  elements: %4u  char_bits: %2u  "
                        "offset_bits: %2u  %s: %5u  codelen: %2u",
                        tree_no, huff_tree->elements, huff_tree->char_bits,
                        huff_tree->offset_bits, huff_tree->counts->tree_buff ?
                        "bufflen" : "min_chr", huff_tree->counts->tree_buff ?
                        int_length : huff_tree->min_chr, huff_tree->height));
    if (verbose >= 2)
      VOID(printf("tree: %2u  elements: %4u  char_bits: %2u  offset_bits: %2u  "
                  "%s: %5u  codelen: %2u\n", tree_no, huff_tree->elements,
                  huff_tree->char_bits, huff_tree->offset_bits,
                  huff_tree->counts->tree_buff ? "bufflen" : "min_chr",
                  huff_tree->counts->tree_buff ? int_length :
                  huff_tree->min_chr, huff_tree->height));

    /* Check that the code tree length matches the element count. */
unknown's avatar
unknown committed
2192 2193
    length=(uint) (offset-packed_tree);
    if (length != huff_tree->elements*2-2)
2194 2195 2196 2197 2198 2199
    {
      VOID(fprintf(stderr, "error: Huff-tree-length: %d != calc_length: %d\n",
                   length, huff_tree->elements * 2 - 2));
      errors++;
      break;
    }
unknown's avatar
unknown committed
2200 2201 2202 2203 2204 2205 2206 2207

    for (i=0 ; i < length ; i++)
    {
      if (packed_tree[i] & IS_OFFSET)
	write_bits(packed_tree[i] - IS_OFFSET+ (1 << huff_tree->offset_bits),
		   huff_tree->offset_bits+1);
      else
	write_bits(packed_tree[i]-huff_tree->min_chr,huff_tree->char_bits+1);
2208 2209 2210 2211 2212 2213 2214 2215 2216
      DBUG_PRINT("info", ("tree[0x%04x]: %s0x%04x",
                          i, (packed_tree[i] & IS_OFFSET) ?
                          " -> " : "", (packed_tree[i] & IS_OFFSET) ?
                          packed_tree[i] - IS_OFFSET + i : packed_tree[i]));
      if (verbose >= 3)
        VOID(printf("tree[0x%04x]: %s0x%04x\n",
                    i, (packed_tree[i] & IS_OFFSET) ? " -> " : "",
                    (packed_tree[i] & IS_OFFSET) ?
                    packed_tree[i] - IS_OFFSET + i : packed_tree[i]));
unknown's avatar
unknown committed
2217 2218
    }
    flush_bits();
2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300

    /*
      Display coding tables and check their correctness.
    */
    codes= huff_tree->counts->tree_buff ? huff_tree->elements : 256;
    for (i= 0; i < codes; i++)
    {
      ulonglong code;
      uint bits;
      uint len;
      uint idx;

      if (! (len= huff_tree->code_len[i]))
        continue;
      DBUG_PRINT("info", ("code[0x%04x]:      0x%s  bits: %2u  bin: %s", i,
                          hexdigits(huff_tree->code[i]), huff_tree->code_len[i],
                          bindigits(huff_tree->code[i],
                                    huff_tree->code_len[i])));
      if (verbose >= 3)
        VOID(printf("code[0x%04x]:      0x%s  bits: %2u  bin: %s\n", i,
                    hexdigits(huff_tree->code[i]), huff_tree->code_len[i],
                    bindigits(huff_tree->code[i], huff_tree->code_len[i])));

      /* Check that the encode table decodes correctly. */
      code= 0;
      bits= 0;
      idx= 0;
      DBUG_EXECUTE_IF("forcechkerr1", len--;);
      DBUG_EXECUTE_IF("forcechkerr2", bits= 8 * sizeof(code););
      DBUG_EXECUTE_IF("forcechkerr3", idx= length;);
      for (;;)
      {
        if (! len)
        {
          VOID(fflush(stdout));
          VOID(fprintf(stderr, "error: code 0x%s with %u bits not found\n",
                       hexdigits(huff_tree->code[i]), huff_tree->code_len[i]));
          errors++;
          break;
        }
        code<<= 1;
        code|= (huff_tree->code[i] >> (--len)) & 1;
        bits++;
        if (bits > 8 * sizeof(code))
        {
          VOID(fflush(stdout));
          VOID(fprintf(stderr, "error: Huffman code too long: %u/%u\n",
                       bits, 8 * sizeof(code)));
          errors++;
          break;
        }
        idx+= code & 1;
        if (idx >= length)
        {
          VOID(fflush(stdout));
          VOID(fprintf(stderr, "error: illegal tree offset: %u/%u\n",
                       idx, length));
          errors++;
          break;
        }
        if (packed_tree[idx] & IS_OFFSET)
          idx+= packed_tree[idx] & ~IS_OFFSET;
        else
          break; /* Hit a leaf. This contains the result value. */
      }
      if (errors)
        break;

      DBUG_EXECUTE_IF("forcechkerr4", packed_tree[idx]++;);
      if (packed_tree[idx] != i)
      {
        VOID(fflush(stdout));
        VOID(fprintf(stderr, "error: decoded value 0x%04x  should be: 0x%04x\n",
                     packed_tree[idx], i));
        errors++;
        break;
      }
    } /*end for (codes)*/
    if (errors)
      break;

    /* Write column values in case of distinct column value compression. */
unknown's avatar
unknown committed
2301 2302 2303
    if (huff_tree->counts->tree_buff)
    {
      for (i=0 ; i < int_length ; i++)
2304 2305 2306 2307 2308 2309 2310 2311
      {
 	write_bits((ulonglong) (uchar) huff_tree->counts->tree_buff[i], 8);
        DBUG_PRINT("info", ("column_values[0x%04x]: 0x%02x",
                            i, (uchar) huff_tree->counts->tree_buff[i]));
        if (verbose >= 3)
          VOID(printf("column_values[0x%04x]: 0x%02x\n",
                      i, (uchar) huff_tree->counts->tree_buff[i]));
      }
unknown's avatar
unknown committed
2312 2313 2314
    }
    flush_bits();
  }
2315 2316 2317
  DBUG_PRINT("info", (""));
  if (verbose >= 2)
    VOID(printf("\n"));
unknown's avatar
unknown committed
2318
  my_afree((gptr) packed_tree);
2319 2320 2321 2322 2323
  if (errors)
  {
    VOID(fprintf(stderr, "Error: Generated decode trees are corrupt. Stop.\n"));
    return 0;
  }
unknown's avatar
unknown committed
2324 2325 2326 2327 2328 2329 2330 2331 2332 2333
  return elements;
}


static uint *make_offset_code_tree(HUFF_TREE *huff_tree, HUFF_ELEMENT *element,
				   uint *offset)
{
  uint *prev_offset;

  prev_offset= offset;
2334 2335 2336 2337 2338 2339 2340 2341
  /*
    'a.leaf.null' takes the same place as 'a.nod.left'. If this is null,
    then there is no left child and, hence no right child either. This
    is a property of a binary tree. An element is either a node with two
    childs, or a leaf without childs.

    The current element is always a node with two childs. Go left first.
  */
unknown's avatar
unknown committed
2342 2343
  if (!element->a.nod.left->a.leaf.null)
  {
2344 2345
    /* Store the byte code or the index of the column value. */
    prev_offset[0] =(uint) element->a.nod.left->a.leaf.element_nr;
unknown's avatar
unknown committed
2346 2347 2348 2349
    offset+=2;
  }
  else
  {
2350 2351 2352 2353
    /*
      Recursively traverse the tree to the left. Mark it as an offset to
      another tree node (in contrast to a byte code or column value index).
    */
unknown's avatar
unknown committed
2354 2355 2356
    prev_offset[0]= IS_OFFSET+2;
    offset=make_offset_code_tree(huff_tree,element->a.nod.left,offset+2);
  }
2357 2358

  /* Now, check the right child. */
unknown's avatar
unknown committed
2359 2360
  if (!element->a.nod.right->a.leaf.null)
  {
2361
    /* Store the byte code or the index of the column value. */
unknown's avatar
unknown committed
2362 2363 2364 2365 2366
    prev_offset[1]=element->a.nod.right->a.leaf.element_nr;
    return offset;
  }
  else
  {
2367 2368 2369 2370
    /*
      Recursively traverse the tree to the right. Mark it as an offset to
      another tree node (in contrast to a byte code or column value index).
    */
unknown's avatar
unknown committed
2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390
    uint temp=(uint) (offset-prev_offset-1);
    prev_offset[1]= IS_OFFSET+ temp;
    if (huff_tree->max_offset < temp)
      huff_tree->max_offset = temp;
    return make_offset_code_tree(huff_tree,element->a.nod.right,offset);
  }
}

	/* Get number of bits neaded to represent value */

static uint max_bit(register uint value)
{
  reg2 uint power=1;

  while ((value>>=1))
    power++;
  return (power);
}


unknown's avatar
unknown committed
2391
static int compress_isam_file(PACK_MRG_INFO *mrg, HUFF_COUNTS *huff_counts)
unknown's avatar
unknown committed
2392 2393 2394 2395 2396
{
  int error;
  uint i,max_calc_length,pack_ref_length,min_record_length,max_record_length,
    intervall,field_length,max_pack_length,pack_blob_length;
  my_off_t record_count;
2397
  char llbuf[32];
unknown's avatar
unknown committed
2398 2399 2400 2401 2402 2403 2404
  ulong length,pack_length;
  byte *record,*pos,*end_pos,*record_pos,*start_pos;
  HUFF_COUNTS *count,*end_count;
  HUFF_TREE *tree;
  MI_INFO *isam_file=mrg->file[0];
  DBUG_ENTER("compress_isam_file");

2405
  /* Allocate a buffer for the records (excluding blobs). */
unknown's avatar
unknown committed
2406 2407
  if (!(record=(byte*) my_alloca(isam_file->s->base.reclength)))
    return -1;
2408

unknown's avatar
unknown committed
2409 2410 2411 2412
  end_count=huff_counts+isam_file->s->base.fields;
  min_record_length= (uint) ~0;
  max_record_length=0;

2413 2414 2415 2416 2417 2418 2419 2420 2421
  /*
    Calculate the maximum number of bits required to pack the records.
    Remember to understand 'max_zero_fill' as 'min_zero_fill'.
    The tree height determines the maximum number of bits per value.
    Some fields skip leading or trailing spaces or zeroes. The skipped
    number of bytes is encoded by 'length_bits' bits.
    Empty blobs and varchar are encoded with a single 1 bit. Other blobs
    and varchar get a leading 0 bit.
  */
unknown's avatar
unknown committed
2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433
  for (i=max_calc_length=0 ; i < isam_file->s->base.fields ; i++)
  {
    if (!(huff_counts[i].pack_type & PACK_TYPE_ZERO_FILL))
      huff_counts[i].max_zero_fill=0;
    if (huff_counts[i].field_type == FIELD_CONSTANT ||
	huff_counts[i].field_type == FIELD_ZERO ||
	huff_counts[i].field_type == FIELD_CHECK)
      continue;
    if (huff_counts[i].field_type == FIELD_INTERVALL)
      max_calc_length+=huff_counts[i].tree->height;
    else if (huff_counts[i].field_type == FIELD_BLOB ||
	     huff_counts[i].field_type == FIELD_VARCHAR)
2434
      max_calc_length+=huff_counts[i].tree->height*huff_counts[i].max_length + huff_counts[i].length_bits +1;
unknown's avatar
unknown committed
2435 2436 2437 2438 2439
    else
      max_calc_length+=
	(huff_counts[i].field_length - huff_counts[i].max_zero_fill)*
	  huff_counts[i].tree->height+huff_counts[i].length_bits;
  }
2440
  max_calc_length= (max_calc_length + 7) / 8;
unknown's avatar
unknown committed
2441 2442 2443 2444 2445 2446
  if (max_calc_length < 254)
    pack_ref_length=1;
  else if (max_calc_length <= 65535)
    pack_ref_length=3;
  else
    pack_ref_length=4;
2447

unknown's avatar
unknown committed
2448
  record_count=0;
2449
  /* 'max_blob_length' is the max length of all blobs of a record. */
unknown's avatar
unknown committed
2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461
  pack_blob_length=0;
  if (isam_file->s->base.blobs)
  {
    if (mrg->max_blob_length < 254)
      pack_blob_length=1;
    else if (mrg->max_blob_length <= 65535)
      pack_blob_length=3;
    else
      pack_blob_length=4;
  }
  max_pack_length=pack_ref_length+pack_blob_length;

2462
  DBUG_PRINT("fields", ("==="));
unknown's avatar
unknown committed
2463 2464 2465 2466 2467 2468
  mrg_reset(mrg);
  while ((error=mrg_rrnd(mrg,record)) != HA_ERR_END_OF_FILE)
  {
    ulong tot_blob_length=0;
    if (! error)
    {
2469
      if (flush_buffer((ulong) max_calc_length + (ulong) max_pack_length))
unknown's avatar
unknown committed
2470 2471 2472 2473 2474 2475 2476 2477
	break;
      record_pos=file_buffer.pos;
      file_buffer.pos+=max_pack_length;
      for (start_pos=record, count= huff_counts; count < end_count ; count++)
      {
	end_pos=start_pos+(field_length=count->field_length);
	tree=count->tree;

2478 2479 2480 2481 2482 2483 2484 2485 2486
        DBUG_PRINT("fields", ("column: %3lu  type: %2u  pack: %2u  zero: %4u  "
                              "lbits: %2u  tree: %2u  length: %4u",
                              (ulong) (count - huff_counts + 1),
                              count->field_type,
                              count->pack_type, count->max_zero_fill,
                              count->length_bits, count->tree->tree_number,
                              count->field_length));

        /* Check if the column contains spaces only. */
unknown's avatar
unknown committed
2487 2488 2489 2490 2491
	if (count->pack_type & PACK_TYPE_SPACE_FIELDS)
	{
	  for (pos=start_pos ; *pos == ' ' && pos < end_pos; pos++) ;
	  if (pos == end_pos)
	  {
2492 2493 2494
            DBUG_PRINT("fields",
                       ("PACK_TYPE_SPACE_FIELDS spaces only, bits:  1"));
            DBUG_PRINT("fields", ("---"));
unknown's avatar
unknown committed
2495 2496 2497 2498
	    write_bits(1,1);
	    start_pos=end_pos;
	    continue;
	  }
2499 2500
          DBUG_PRINT("fields",
                     ("PACK_TYPE_SPACE_FIELDS not only spaces, bits:  1"));
unknown's avatar
unknown committed
2501 2502 2503 2504 2505 2506
	  write_bits(0,1);
	}
	end_pos-=count->max_zero_fill;
	field_length-=count->max_zero_fill;

	switch(count->field_type) {
unknown's avatar
unknown committed
2507
	case FIELD_SKIP_ZERO:
unknown's avatar
unknown committed
2508 2509
	  if (!memcmp((byte*) start_pos,zero_string,field_length))
	  {
2510
            DBUG_PRINT("fields", ("FIELD_SKIP_ZERO zeroes only, bits:  1"));
unknown's avatar
unknown committed
2511 2512 2513 2514
	    write_bits(1,1);
	    start_pos=end_pos;
	    break;
	  }
2515
          DBUG_PRINT("fields", ("FIELD_SKIP_ZERO not only zeroes, bits:  1"));
unknown's avatar
unknown committed
2516 2517 2518
	  write_bits(0,1);
	  /* Fall through */
	case FIELD_NORMAL:
2519 2520
          DBUG_PRINT("fields", ("FIELD_NORMAL %lu bytes",
                                (ulong) (end_pos - start_pos)));
unknown's avatar
unknown committed
2521
	  for ( ; start_pos < end_pos ; start_pos++)
2522 2523 2524 2525 2526 2527 2528 2529
          {
            DBUG_PRINT("fields",
                       ("value: 0x%02x  code: 0x%s  bits: %2u  bin: %s",
                        (uchar) *start_pos,
                        hexdigits(tree->code[(uchar) *start_pos]),
                        (uint) tree->code_len[(uchar) *start_pos],
                        bindigits(tree->code[(uchar) *start_pos],
                                  (uint) tree->code_len[(uchar) *start_pos])));
unknown's avatar
unknown committed
2530 2531
	    write_bits(tree->code[(uchar) *start_pos],
		       (uint) tree->code_len[(uchar) *start_pos]);
2532
          }
unknown's avatar
unknown committed
2533
	  break;
unknown's avatar
unknown committed
2534
	case FIELD_SKIP_ENDSPACE:
unknown's avatar
unknown committed
2535
	  for (pos=end_pos ; pos > start_pos && pos[-1] == ' ' ; pos--) ;
2536
	  length= (ulong) (end_pos - pos);
unknown's avatar
unknown committed
2537 2538 2539 2540
	  if (count->pack_type & PACK_TYPE_SELECTED)
	  {
	    if (length > count->min_space)
	    {
2541 2542 2543 2544 2545
              DBUG_PRINT("fields",
                         ("FIELD_SKIP_ENDSPACE more than min_space, bits:  1"));
              DBUG_PRINT("fields",
                         ("FIELD_SKIP_ENDSPACE skip %lu/%u bytes, bits: %2u",
                          length, field_length, count->length_bits));
unknown's avatar
unknown committed
2546 2547 2548 2549 2550
	      write_bits(1,1);
	      write_bits(length,count->length_bits);
	    }
	    else
	    {
2551 2552 2553
              DBUG_PRINT("fields",
                         ("FIELD_SKIP_ENDSPACE not more than min_space, "
                          "bits:  1"));
unknown's avatar
unknown committed
2554 2555 2556 2557 2558
	      write_bits(0,1);
	      pos=end_pos;
	    }
	  }
	  else
2559 2560 2561 2562
          {
            DBUG_PRINT("fields",
                       ("FIELD_SKIP_ENDSPACE skip %lu/%u bytes, bits: %2u",
                        length, field_length, count->length_bits));
unknown's avatar
unknown committed
2563
	    write_bits(length,count->length_bits);
2564 2565 2566 2567
          }
          /* Encode all significant bytes. */
          DBUG_PRINT("fields", ("FIELD_SKIP_ENDSPACE %lu bytes",
                                (ulong) (pos - start_pos)));
unknown's avatar
unknown committed
2568
	  for ( ; start_pos < pos ; start_pos++)
2569 2570 2571 2572 2573 2574 2575 2576
          {
            DBUG_PRINT("fields",
                       ("value: 0x%02x  code: 0x%s  bits: %2u  bin: %s",
                        (uchar) *start_pos,
                        hexdigits(tree->code[(uchar) *start_pos]),
                        (uint) tree->code_len[(uchar) *start_pos],
                        bindigits(tree->code[(uchar) *start_pos],
                                  (uint) tree->code_len[(uchar) *start_pos])));
unknown's avatar
unknown committed
2577 2578
	    write_bits(tree->code[(uchar) *start_pos],
		       (uint) tree->code_len[(uchar) *start_pos]);
2579
          }
unknown's avatar
unknown committed
2580 2581
	  start_pos=end_pos;
	  break;
unknown's avatar
unknown committed
2582
	case FIELD_SKIP_PRESPACE:
unknown's avatar
unknown committed
2583
	  for (pos=start_pos ; pos < end_pos && pos[0] == ' ' ; pos++) ;
2584
          length= (ulong) (pos - start_pos);
unknown's avatar
unknown committed
2585 2586 2587 2588
	  if (count->pack_type & PACK_TYPE_SELECTED)
	  {
	    if (length > count->min_space)
	    {
2589 2590 2591 2592 2593
              DBUG_PRINT("fields",
                         ("FIELD_SKIP_PRESPACE more than min_space, bits:  1"));
              DBUG_PRINT("fields",
                         ("FIELD_SKIP_PRESPACE skip %lu/%u bytes, bits: %2u",
                          length, field_length, count->length_bits));
unknown's avatar
unknown committed
2594 2595 2596 2597 2598
	      write_bits(1,1);
	      write_bits(length,count->length_bits);
	    }
	    else
	    {
2599 2600 2601
              DBUG_PRINT("fields",
                         ("FIELD_SKIP_PRESPACE not more than min_space, "
                          "bits:  1"));
unknown's avatar
unknown committed
2602 2603 2604 2605 2606
	      pos=start_pos;
	      write_bits(0,1);
	    }
	  }
	  else
2607 2608 2609 2610
          {
            DBUG_PRINT("fields",
                       ("FIELD_SKIP_PRESPACE skip %lu/%u bytes, bits: %2u",
                        length, field_length, count->length_bits));
unknown's avatar
unknown committed
2611
	    write_bits(length,count->length_bits);
2612 2613 2614 2615
          }
          /* Encode all significant bytes. */
          DBUG_PRINT("fields", ("FIELD_SKIP_PRESPACE %lu bytes",
                                (ulong) (end_pos - start_pos)));
unknown's avatar
unknown committed
2616
	  for (start_pos=pos ; start_pos < end_pos ; start_pos++)
2617 2618 2619 2620 2621 2622 2623 2624
          {
            DBUG_PRINT("fields",
                       ("value: 0x%02x  code: 0x%s  bits: %2u  bin: %s",
                        (uchar) *start_pos,
                        hexdigits(tree->code[(uchar) *start_pos]),
                        (uint) tree->code_len[(uchar) *start_pos],
                        bindigits(tree->code[(uchar) *start_pos],
                                  (uint) tree->code_len[(uchar) *start_pos])));
unknown's avatar
unknown committed
2625 2626
	    write_bits(tree->code[(uchar) *start_pos],
		       (uint) tree->code_len[(uchar) *start_pos]);
2627
          }
unknown's avatar
unknown committed
2628 2629 2630 2631
	  break;
	case FIELD_CONSTANT:
	case FIELD_ZERO:
	case FIELD_CHECK:
2632
          DBUG_PRINT("fields", ("FIELD_CONSTANT/ZERO/CHECK"));
unknown's avatar
unknown committed
2633 2634 2635 2636
	  start_pos=end_pos;
	  break;
	case FIELD_INTERVALL:
	  global_count=count;
2637 2638
	  pos=(byte*) tree_search(&count->int_tree, start_pos,
				  count->int_tree.custom_arg);
unknown's avatar
unknown committed
2639
	  intervall=(uint) (pos - count->tree_buff)/field_length;
2640 2641 2642 2643
          DBUG_PRINT("fields", ("FIELD_INTERVALL"));
          DBUG_PRINT("fields", ("index: %4u code: 0x%s  bits: %2u",
                                intervall, hexdigits(tree->code[intervall]),
                                (uint) tree->code_len[intervall]));
unknown's avatar
unknown committed
2644 2645 2646 2647 2648 2649 2650 2651
	  write_bits(tree->code[intervall],(uint) tree->code_len[intervall]);
	  start_pos=end_pos;
	  break;
	case FIELD_BLOB:
	{
	  ulong blob_length=_mi_calc_blob_length(field_length-
						 mi_portable_sizeof_char_ptr,
						 start_pos);
2652
          /* Empty blobs are encoded with a single 1 bit. */
unknown's avatar
unknown committed
2653 2654
	  if (!blob_length)
	  {
2655 2656
            DBUG_PRINT("fields", ("FIELD_BLOB empty, bits:  1"));
            write_bits(1,1);
unknown's avatar
unknown committed
2657 2658 2659 2660
	  }
	  else
	  {
	    byte *blob,*blob_end;
2661
            DBUG_PRINT("fields", ("FIELD_BLOB not empty, bits:  1"));
unknown's avatar
unknown committed
2662
	    write_bits(0,1);
2663 2664 2665
            /* Write the blob length. */
            DBUG_PRINT("fields", ("FIELD_BLOB %lu bytes, bits: %2u",
                                  blob_length, count->length_bits));
unknown's avatar
unknown committed
2666 2667 2668 2669
	    write_bits(blob_length,count->length_bits);
	    memcpy_fixed(&blob,end_pos-mi_portable_sizeof_char_ptr,
			 sizeof(char*));
	    blob_end=blob+blob_length;
2670
            /* Encode the blob bytes. */
unknown's avatar
unknown committed
2671
	    for ( ; blob < blob_end ; blob++)
2672 2673 2674 2675 2676 2677 2678
            {
              DBUG_PRINT("fields",
                         ("value: 0x%02x  code: 0x%s  bits: %2u  bin: %s",
                          (uchar) *blob, hexdigits(tree->code[(uchar) *blob]),
                          (uint) tree->code_len[(uchar) *blob],
                          bindigits(tree->code[(uchar) *start_pos],
                                    (uint)tree->code_len[(uchar) *start_pos])));
unknown's avatar
unknown committed
2679 2680
	      write_bits(tree->code[(uchar) *blob],
			 (uint) tree->code_len[(uchar) *blob]);
2681
            }
unknown's avatar
unknown committed
2682 2683 2684 2685 2686 2687 2688
	    tot_blob_length+=blob_length;
	  }
	  start_pos= end_pos;
	  break;
	}
	case FIELD_VARCHAR:
	{
2689 2690 2691
          uint pack_length= HA_VARCHAR_PACKLENGTH(count->field_length-1);
	  ulong col_length= (pack_length == 1 ? (uint) *(uchar*) start_pos :
                             uint2korr(start_pos));
2692
          /* Empty varchar are encoded with a single 1 bit. */
unknown's avatar
unknown committed
2693 2694
	  if (!col_length)
	  {
2695
            DBUG_PRINT("fields", ("FIELD_VARCHAR empty, bits:  1"));
unknown's avatar
unknown committed
2696 2697 2698 2699
	    write_bits(1,1);			/* Empty varchar */
	  }
	  else
	  {
2700
	    byte *end=start_pos+pack_length+col_length;
2701
            DBUG_PRINT("fields", ("FIELD_VARCHAR not empty, bits:  1"));
unknown's avatar
unknown committed
2702
	    write_bits(0,1);
2703 2704 2705
            /* Write the varchar length. */
            DBUG_PRINT("fields", ("FIELD_VARCHAR %lu bytes, bits: %2u",
                                  col_length, count->length_bits));
unknown's avatar
unknown committed
2706
	    write_bits(col_length,count->length_bits);
2707
            /* Encode the varchar bytes. */
2708
	    for (start_pos+=pack_length ; start_pos < end ; start_pos++)
2709 2710 2711 2712 2713 2714 2715 2716
            {
              DBUG_PRINT("fields",
                         ("value: 0x%02x  code: 0x%s  bits: %2u  bin: %s",
                          (uchar) *start_pos,
                          hexdigits(tree->code[(uchar) *start_pos]),
                          (uint) tree->code_len[(uchar) *start_pos],
                          bindigits(tree->code[(uchar) *start_pos],
                                    (uint)tree->code_len[(uchar) *start_pos])));
unknown's avatar
unknown committed
2717 2718
	      write_bits(tree->code[(uchar) *start_pos],
			 (uint) tree->code_len[(uchar) *start_pos]);
2719
            }
unknown's avatar
unknown committed
2720 2721 2722 2723 2724 2725 2726 2727
	  }
	  start_pos= end_pos;
	  break;
	}
	case FIELD_LAST:
	  abort();				/* Impossible */
	}
	start_pos+=count->max_zero_fill;
2728
        DBUG_PRINT("fields", ("---"));
unknown's avatar
unknown committed
2729 2730
      }
      flush_bits();
2731
      length=(ulong) ((byte*) file_buffer.pos - record_pos) - max_pack_length;
unknown's avatar
unknown committed
2732 2733 2734
      pack_length=save_pack_length(record_pos,length);
      if (pack_blob_length)
	pack_length+=save_pack_length(record_pos+pack_length,tot_blob_length);
2735 2736 2737 2738
      DBUG_PRINT("fields", ("record: %lu  length: %lu  blob-length: %lu  "
                            "length-bytes: %lu", (ulong) record_count, length,
                            tot_blob_length, pack_length));
      DBUG_PRINT("fields", ("==="));
unknown's avatar
unknown committed
2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749

      /* Correct file buffer if the header was smaller */
      if (pack_length != max_pack_length)
      {
	bmove(record_pos+pack_length,record_pos+max_pack_length,length);
	file_buffer.pos-= (max_pack_length-pack_length);
      }
      if (length < (ulong) min_record_length)
	min_record_length=(uint) length;
      if (length > (ulong) max_record_length)
	max_record_length=(uint) length;
2750 2751
      record_count++;
      if (write_loop && record_count % WRITE_COUNT == 0)
unknown's avatar
unknown committed
2752
      {
2753 2754
	VOID(printf("%lu\r", (ulong) record_count));
        VOID(fflush(stdout));
unknown's avatar
unknown committed
2755 2756 2757 2758 2759 2760 2761 2762 2763
      }
    }
    else if (error != HA_ERR_RECORD_DELETED)
      break;
  }
  if (error == HA_ERR_END_OF_FILE)
    error=0;
  else
  {
2764 2765
    VOID(fprintf(stderr, "%s: Got error %d reading records\n",
                 my_progname, error));
unknown's avatar
unknown committed
2766
  }
2767 2768
  if (verbose >= 2)
    VOID(printf("wrote %s records.\n", llstr((longlong) record_count, llbuf)));
unknown's avatar
unknown committed
2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807

  my_afree((gptr) record);
  mrg->ref_length=max_pack_length;
  mrg->min_pack_length=max_record_length ? min_record_length : 0;
  mrg->max_pack_length=max_record_length;
  DBUG_RETURN(error || error_on_write || flush_buffer(~(ulong) 0));
}


static char *make_new_name(char *new_name, char *old_name)
{
  return fn_format(new_name,old_name,"",DATA_TMP_EXT,2+4);
}

static char *make_old_name(char *new_name, char *old_name)
{
  return fn_format(new_name,old_name,"",OLD_EXT,2+4);
}

	/* rutines for bit writing buffer */

static void init_file_buffer(File file, pbool read_buffer)
{
  file_buffer.file=file;
  file_buffer.buffer=my_malloc(ALIGN_SIZE(RECORD_CACHE_SIZE),MYF(MY_WME));
  file_buffer.end=file_buffer.buffer+ALIGN_SIZE(RECORD_CACHE_SIZE)-8;
  file_buffer.pos_in_file=0;
  error_on_write=0;
  if (read_buffer)
  {

    file_buffer.pos=file_buffer.end;
    file_buffer.bits=0;
  }
  else
  {
    file_buffer.pos=file_buffer.buffer;
    file_buffer.bits=BITS_SAVED;
  }
2808
  file_buffer.bitbucket= 0;
unknown's avatar
unknown committed
2809 2810 2811 2812 2813 2814
}


static int flush_buffer(ulong neaded_length)
{
  ulong length;
2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828

  /*
    file_buffer.end is 8 bytes lower than the real end of the buffer.
    This is done so that the end-of-buffer condition does not need to be
    checked for every byte (see write_bits()). Consequently,
    file_buffer.pos can become greater than file_buffer.end. The
    algorithms in the other functions ensure that there will never be
    more than 8 bytes written to the buffer without an end-of-buffer
    check. So the buffer cannot be overrun. But we need to check for the
    near-to-buffer-end condition to avoid a negative result, which is
    casted to unsigned and thus becomes giant.
  */
  if ((file_buffer.pos < file_buffer.end) &&
      ((ulong) (file_buffer.end - file_buffer.pos) > neaded_length))
unknown's avatar
unknown committed
2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850
    return 0;
  length=(ulong) (file_buffer.pos-file_buffer.buffer);
  file_buffer.pos=file_buffer.buffer;
  file_buffer.pos_in_file+=length;
  if (test_only)
    return 0;
  if (error_on_write|| my_write(file_buffer.file,file_buffer.buffer,
				length,
				MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)))
  {
    error_on_write=1;
    return 1;
  }

  if (neaded_length != ~(ulong) 0 &&
      (ulong) (file_buffer.end-file_buffer.buffer) < neaded_length)
  {
    char *tmp;
    neaded_length+=256;				/* some margin */
    tmp=my_realloc(file_buffer.buffer, neaded_length,MYF(MY_WME));
    if (!tmp)
      return 1;
2851 2852
    file_buffer.pos= ((uchar*) tmp +
                      (ulong) (file_buffer.pos - file_buffer.buffer));
unknown's avatar
unknown committed
2853 2854 2855 2856 2857 2858 2859 2860 2861 2862 2863 2864 2865 2866
    file_buffer.buffer=tmp;
    file_buffer.end=tmp+neaded_length-8;
  }
  return 0;
}


static void end_file_buffer(void)
{
  my_free((gptr) file_buffer.buffer,MYF(0));
}

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

2867
static void write_bits(register ulonglong value, register uint bits)
unknown's avatar
unknown committed
2868
{
2869 2870 2871 2872
  DBUG_ASSERT(((bits < 8 * sizeof(value)) && ! (value >> bits)) ||
              (bits == 8 * sizeof(value)));

  if ((file_buffer.bits-= (int) bits) >= 0)
unknown's avatar
unknown committed
2873
  {
2874
    file_buffer.bitbucket|= value << file_buffer.bits;
unknown's avatar
unknown committed
2875 2876 2877
  }
  else
  {
2878
    reg3 ulonglong bit_buffer;
unknown's avatar
unknown committed
2879
    bits= (uint) -file_buffer.bits;
2880 2881 2882 2883 2884 2885 2886
    bit_buffer= (file_buffer.bitbucket |
                 ((bits != 8 * sizeof(value)) ? (value >> bits) : 0));
#if BITS_SAVED == 64
    *file_buffer.pos++= (uchar) (bit_buffer >> 56);
    *file_buffer.pos++= (uchar) (bit_buffer >> 48);
    *file_buffer.pos++= (uchar) (bit_buffer >> 40);
    *file_buffer.pos++= (uchar) (bit_buffer >> 32);
unknown's avatar
unknown committed
2887
#endif
2888 2889 2890 2891
    *file_buffer.pos++= (uchar) (bit_buffer >> 24);
    *file_buffer.pos++= (uchar) (bit_buffer >> 16);
    *file_buffer.pos++= (uchar) (bit_buffer >> 8);
    *file_buffer.pos++= (uchar) (bit_buffer);
unknown's avatar
unknown committed
2892

2893
    if (bits != 8 * sizeof(value))
2894
      value&= (((ulonglong) 1) << bits) - 1;
unknown's avatar
unknown committed
2895
    if (file_buffer.pos >= file_buffer.end)
2896
      VOID(flush_buffer(~ (ulong) 0));
unknown's avatar
unknown committed
2897
    file_buffer.bits=(int) (BITS_SAVED - bits);
2898
    file_buffer.bitbucket= value << (BITS_SAVED - bits);
unknown's avatar
unknown committed
2899 2900 2901 2902 2903 2904
  }
  return;
}

	/* Flush bits in bit_buffer to buffer */

2905
static void flush_bits(void)
unknown's avatar
unknown committed
2906
{
2907 2908
  int bits;
  ulonglong bit_buffer;
unknown's avatar
unknown committed
2909

2910 2911 2912
  bits= file_buffer.bits & ~7;
  bit_buffer= file_buffer.bitbucket >> bits;
  bits= BITS_SAVED - bits;
unknown's avatar
unknown committed
2913 2914
  while (bits > 0)
  {
2915 2916
    bits-= 8;
    *file_buffer.pos++= (uchar) (bit_buffer >> bits);
unknown's avatar
unknown committed
2917
  }
2918 2919
  file_buffer.bits= BITS_SAVED;
  file_buffer.bitbucket= 0;
unknown's avatar
unknown committed
2920 2921 2922 2923 2924 2925 2926
}


/****************************************************************************
** functions to handle the joined files
****************************************************************************/

unknown's avatar
unknown committed
2927
static int save_state(MI_INFO *isam_file,PACK_MRG_INFO *mrg,my_off_t new_length,
unknown's avatar
unknown committed
2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942 2943
		      ha_checksum crc)
{
  MYISAM_SHARE *share=isam_file->s;
  uint options=mi_uint2korr(share->state.header.options);
  uint key;
  DBUG_ENTER("save_state");

  options|= HA_OPTION_COMPRESS_RECORD | HA_OPTION_READ_ONLY_DATA;
  mi_int2store(share->state.header.options,options);

  share->state.state.data_file_length=new_length;
  share->state.state.del=0;
  share->state.state.empty=0;
  share->state.dellink= HA_OFFSET_ERROR;
  share->state.split=(ha_rows) mrg->records;
  share->state.version=(ulong) time((time_t*) 0);
2944
  if (share->state.key_map != (ULL(1) << share->base.keys) - 1)
unknown's avatar
unknown committed
2945 2946 2947 2948 2949 2950 2951 2952
  {
    /*
      Some indexes are disabled, cannot use current key_file_length value
      as an estimate of upper bound of index file size. Use packed data file 
      size instead.
    */
    share->state.state.key_file_length= new_length;
  }
unknown's avatar
unknown committed
2953
  /*
unknown's avatar
unknown committed
2954 2955 2956
    If there are no disabled indexes, keep key_file_length value from 
    original file so "myisamchk -rq" can use this value (this is necessary 
    because index size cannot be easily calculated for fulltext keys)
unknown's avatar
unknown committed
2957
  */
unknown's avatar
unknown committed
2958
  share->state.key_map=0;
unknown's avatar
unknown committed
2959 2960 2961 2962 2963 2964 2965 2966
  for (key=0 ; key < share->base.keys ; key++)
    share->state.key_root[key]= HA_OFFSET_ERROR;
  for (key=0 ; key < share->state.header.max_block_size ; key++)
    share->state.key_del[key]= HA_OFFSET_ERROR;
  share->state.checksum=crc;		/* Save crc here */
  share->changed=1;			/* Force write of header */
  share->state.open_count=0;
  share->global_changed=0;
unknown's avatar
unknown committed
2967
  VOID(my_chsize(share->kfile, share->base.keystart, 0, MYF(0)));
unknown's avatar
unknown committed
2968 2969 2970 2971 2972 2973
  if (share->base.keys)
    isamchk_neaded=1;
  DBUG_RETURN(mi_state_info_write(share->kfile,&share->state,1+2));
}


unknown's avatar
unknown committed
2974
static int save_state_mrg(File file,PACK_MRG_INFO *mrg,my_off_t new_length,
unknown's avatar
unknown committed
2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989
			  ha_checksum crc)
{
  MI_STATE_INFO state;
  MI_INFO *isam_file=mrg->file[0];
  uint options;
  DBUG_ENTER("save_state_mrg");

  state= isam_file->s->state;
  options= (mi_uint2korr(state.header.options) | HA_OPTION_COMPRESS_RECORD |
	    HA_OPTION_READ_ONLY_DATA);
  mi_int2store(state.header.options,options);
  state.state.data_file_length=new_length;
  state.state.del=0;
  state.state.empty=0;
  state.state.records=state.split=(ha_rows) mrg->records;
unknown's avatar
unknown committed
2990 2991 2992 2993 2994 2995
  /* See comment above in save_state about key_file_length handling. */
  if (mrg->src_file_has_indexes_disabled)
  {
    isam_file->s->state.state.key_file_length=
      max(isam_file->s->state.state.key_file_length, new_length);
  }
unknown's avatar
unknown committed
2996 2997 2998 2999 3000 3001
  state.dellink= HA_OFFSET_ERROR;
  state.version=(ulong) time((time_t*) 0);
  state.key_map=0;
  state.checksum=crc;
  if (isam_file->s->base.keys)
    isamchk_neaded=1;
unknown's avatar
unknown committed
3002
  state.changed=STATE_CHANGED | STATE_NOT_ANALYZED; /* Force check of table */
unknown's avatar
unknown committed
3003 3004 3005 3006 3007 3008
  DBUG_RETURN (mi_state_info_write(file,&state,1+2));
}


/* reset for mrg_rrnd */

unknown's avatar
unknown committed
3009
static void mrg_reset(PACK_MRG_INFO *mrg)
unknown's avatar
unknown committed
3010 3011 3012
{
  if (mrg->current)
  {
unknown's avatar
unknown committed
3013
    mi_extra(*mrg->current, HA_EXTRA_NO_CACHE, 0);
unknown's avatar
unknown committed
3014 3015 3016 3017
    mrg->current=0;
  }
}

unknown's avatar
unknown committed
3018
static int mrg_rrnd(PACK_MRG_INFO *info,byte *buf)
unknown's avatar
unknown committed
3019 3020 3021 3022 3023 3024 3025 3026 3027
{
  int error;
  MI_INFO *isam_info;
  my_off_t filepos;

  if (!info->current)
  {
    isam_info= *(info->current=info->file);
    info->end=info->current+info->count;
unknown's avatar
unknown committed
3028 3029
    mi_extra(isam_info, HA_EXTRA_RESET, 0);
    mi_extra(isam_info, HA_EXTRA_CACHE, 0);
unknown's avatar
unknown committed
3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 3043 3044
    filepos=isam_info->s->pack.header_length;
  }
  else
  {
    isam_info= *info->current;
    filepos= isam_info->nextpos;
  }

  for (;;)
  {
    isam_info->update&= HA_STATE_CHANGED;
    if (!(error=(*isam_info->s->read_rnd)(isam_info,(byte*) buf,
					  filepos, 1)) ||
	error != HA_ERR_END_OF_FILE)
      return (error);
unknown's avatar
unknown committed
3045
    mi_extra(isam_info,HA_EXTRA_NO_CACHE, 0);
unknown's avatar
unknown committed
3046 3047 3048 3049 3050
    if (info->current+1 == info->end)
      return(HA_ERR_END_OF_FILE);
    info->current++;
    isam_info= *info->current;
    filepos=isam_info->s->pack.header_length;
unknown's avatar
unknown committed
3051 3052
    mi_extra(isam_info,HA_EXTRA_RESET, 0);
    mi_extra(isam_info,HA_EXTRA_CACHE, 0);
unknown's avatar
unknown committed
3053 3054 3055 3056
  }
}


unknown's avatar
unknown committed
3057
static int mrg_close(PACK_MRG_INFO *mrg)
unknown's avatar
unknown committed
3058 3059 3060 3061 3062 3063 3064 3065 3066
{
  uint i;
  int error=0;
  for (i=0 ; i < mrg->count ; i++)
    error|=mi_close(mrg->file[i]);
  if (mrg->free_file)
    my_free((gptr) mrg->file,MYF(0));
  return error;
}
3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133 3134 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191 3192 3193 3194


#if !defined(DBUG_OFF)
/*
  Fake the counts to get big Huffman codes.

  SYNOPSIS
    fakebigcodes()
    huff_counts                 A pointer to the counts array.
    end_count                   A pointer past the counts array.

  DESCRIPTION

    Huffman coding works by removing the two least frequent values from
    the list of values and add a new value with the sum of their
    incidences in a loop until only one value is left. Every time a
    value is reused for a new value, it gets one more bit for its
    encoding. Hence, the least frequent values get the longest codes.

    To get a maximum code length for a value, two of the values must
    have an incidence of 1. As their sum is 2, the next infrequent value
    must have at least an incidence of 2, then 4, 8, 16 and so on. This
    means that one needs 2**n bytes (values) for a code length of n
    bits. However, using more distinct values forces the use of longer
    codes, or reaching the code length with less total bytes (values).

    To get 64(32)-bit codes, I sort the counts by decreasing incidence.
    I assign counts of 1 to the two most frequent values, a count of 2
    for the next one, then 4, 8, and so on until 2**64-1(2**30-1). All
    the remaining values get 1. That way every possible byte has an
    assigned code, though not all codes are used if not all byte values
    are present in the column.

    This strategy would work with distinct column values too, but
    requires that at least 64(32) values are present. To make things
    easier here, I cancel all distinct column values and force byte
    compression for all columns.

  RETURN
    void
*/

static void fakebigcodes(HUFF_COUNTS *huff_counts, HUFF_COUNTS *end_count)
{
  HUFF_COUNTS   *count;
  my_off_t      *cur_count_p;
  my_off_t      *end_count_p;
  my_off_t      **cur_sort_p;
  my_off_t      **end_sort_p;
  my_off_t      *sort_counts[256];
  my_off_t      total;
  DBUG_ENTER("fakebigcodes");

  for (count= huff_counts; count < end_count; count++)
  {
    /*
      Remove distinct column values.
    */
    if (huff_counts->tree_buff)
    {
      my_free((gptr) huff_counts->tree_buff, MYF(0));
      delete_tree(&huff_counts->int_tree);
      huff_counts->tree_buff= NULL;
      DBUG_PRINT("fakebigcodes", ("freed distinct column values"));
    }

    /*
      Sort counts by decreasing incidence.
    */
    cur_count_p= count->counts;
    end_count_p= cur_count_p + 256;
    cur_sort_p= sort_counts;
    while (cur_count_p < end_count_p)
      *(cur_sort_p++)= cur_count_p++;
    (void) qsort(sort_counts, 256, sizeof(my_off_t*), (qsort_cmp) fakecmp);

    /*
      Assign faked counts.
    */
    cur_sort_p= sort_counts;
#if SIZEOF_LONG_LONG > 4
    end_sort_p= sort_counts + 8 * sizeof(ulonglong) - 1;
#else
    end_sort_p= sort_counts + 8 * sizeof(ulonglong) - 2;
#endif
    /* Most frequent value gets a faked count of 1. */
    **(cur_sort_p++)= 1;
    total= 1;
    while (cur_sort_p < end_sort_p)
    {
      **(cur_sort_p++)= total;
      total<<= 1;
    }
    /* Set the last value. */
    **(cur_sort_p++)= --total;
    /*
      Set the remaining counts.
    */
    end_sort_p= sort_counts + 256;
    while (cur_sort_p < end_sort_p)
      **(cur_sort_p++)= 1;
  }
  DBUG_VOID_RETURN;
}


/*
  Compare two counts for reverse sorting.

  SYNOPSIS
    fakecmp()
    count1              One count.
    count2              Another count.

  RETURN
    1                   count1  < count2
    0                   count1 == count2
    -1                  count1 >  count2
*/

static int fakecmp(my_off_t **count1, my_off_t **count2)
{
  return ((**count1 < **count2) ? 1 :
          (**count1 > **count2) ? -1 : 0);
}
#endif