cde/programs/dtinfo/DtMmdb/compression/huffman.C

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /*
  24  * $XConsortium: huffman.cc /main/3 1996/06/11 17:15:06 cde-hal $
  25  *
  26  * Copyright (c) 1993 HAL Computer Systems International, Ltd.
  27  * All rights reserved.  Unpublished -- rights reserved under
  28  * the Copyright Laws of the United States.  USE OF A COPYRIGHT
  29  * NOTICE IS PRECAUTIONARY ONLY AND DOES NOT IMPLY PUBLICATION
  30  * OR DISCLOSURE.
  31  *
  32  * THIS SOFTWARE CONTAINS CONFIDENTIAL INFORMATION AND TRADE
  33  * SECRETS OF HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.  USE,
  34  * DISCLOSURE, OR REPRODUCTION IS PROHIBITED WITHOUT THE
  35  * PRIOR EXPRESS WRITTEN PERMISSION OF HAL COMPUTER SYSTEMS
  36  * INTERNATIONAL, LTD.
  37  *
  38  *                         RESTRICTED RIGHTS LEGEND
  39  * Use, duplication, or disclosure by the Government is subject
  40  * to the restrictions as set forth in subparagraph (c)(l)(ii)
  41  * of the Rights in Technical Data and Computer Software clause
  42  * at DFARS 252.227-7013.
  43  *
  44  *          HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.
  45  *                  1315 Dell Avenue
  46  *                  Campbell, CA  95008
  47  *
  48  */
  49
  50
  51 #include "compression/huffman.h"
  52 #include "dstr/heap.h"
  53
  54 ////////////////////////////////////////
  55 //
  56 ////////////////////////////////////////
  57
  58 htr_node::htr_node(encoding_unit* e, htr_node* lt, htr_node* rt):
  59    left(lt), right(rt), eu(e), freq(e->freq), parent(0)
  60 {
  61 }
  62
  63 htr_node::htr_node(unsigned long f, htr_node* lt, htr_node* rt):
  64    left(lt), right(rt), eu(0), freq(f), parent(0)
  65 {
  66 }
  67
  68 htr_node::~htr_node()
  69 {
  70    delete left;
  71    delete right;
  72 }
  73
  74 ////////////////////////////////////////
  75 //
  76 ////////////////////////////////////////
  77 Boolean htr_eq(const void* n1, const void* n2)
  78 {
  79    if ( ((htr_node*)n1) -> freq == ((htr_node*)n2) -> freq )
  80      return true;
  81    else
  82      return false;
  83 }
  84
  85 Boolean htr_ls(const void* n1, const void* n2)
  86 {
  87    if ( ((htr_node*)n1) -> freq > ((htr_node*)n2) -> freq )
  88      return true;
  89    else
  90      return false;
  91 }
  92
  93 ////////////////////////////////////////
  94 //
  95 ////////////////////////////////////////
  96 huff::huff(): compress_agent(HUFFMAN_AGENT_CODE),
  97    e_units(0), cts(0), tri(new trie(26)), htr_root(0)
  98 {
  99 }
 100
 101 huff::~huff()
 102 {
 103    delete tri;
 104    delete htr_root;
 105 }
 106
 107 void huff::build_tree()
 108 {
 109    heap htr_node_set(htr_eq, htr_ls, cts);
 110
 111    htr_node* x ;
 112    for (int i=0; i<cts; i++ ) {
 113       if ( e_units[i] ) {
 114          x = new htr_node(e_units[i]);
 115          e_units[i] -> leaf_htr_node = x;
 116          htr_node_set.insert(x);
 117       }
 118    }
 119
 120    htr_node_set.heapify();
 121
 122    htr_node *n1, *n2, *n3;
 123    while ( htr_node_set.count() > 1 ) {
 124
 125 // max is the smallest element. see htr_ls()
 126       n1 = (htr_node*)htr_node_set.max_elm() ;
 127       htr_node_set.delete_max() ;
 128
 129 // max is the smallest element. see htr_ls()
 130       n2 = (htr_node*)htr_node_set.max_elm() ;
 131       htr_node_set.delete_max() ;
 132
 133       n3 = new htr_node(n1->freq+n2->freq, n1, n2);
 134
 135       n1 -> parent = n2 -> parent = n3;
 136
 137       htr_node_set.insert_heapify(n3);
 138    }
 139
 140    htr_root = (htr_node*)htr_node_set.max_elm();
 141    htr_node_set.delete_max() ;
 142 }
 143
 144 void huff::calculate_code()
 145 {
 146    htr_node* x ;
 147    htr_node* parent;
 148
 149    for (int i=0; i<cts; i++ ) {
 150
 151       if ( e_units[i] == 0 )
 152          continue;
 153
 154       e_units[i] -> code = 0;
 155       e_units[i] -> bits = 0;
 156
 157       x = e_units[i] -> leaf_htr_node;
 158
 159       while ( x ) {
 160          parent = x -> parent;
 161
 162          if ( parent == 0 )
 163             break;
 164
 165          e_units[i] -> code >>= 1;
 166
 167          if ( parent -> left == x ) {
 168             e_units[i] -> code |= 0x80000000;
 169          } else
 170          if ( parent -> right != x ) {
 171             debug(cerr, i);
 172             throw(stringException("huffman tree corrupted"));
 173          }
 174
 175          x = parent;
 176          e_units[i] -> bits++;
 177
 178          if ( e_units[i] -> bits > BITS_IN(unsigned long) ) {
 179             debug(cerr, e_units[i] -> bits);
 180             throw(stringException("huffman tree too deep"));
 181          }
 182       }
 183
 184       e_units[i] -> code >>= ( 32 - e_units[i] -> bits );
 185 //debug(cerr, hex(e_units[i] -> code));
 186    }
 187 }
 188
 189 ostream& huff::print_alphabet(ostream& out)
 190 {
 191    unsigned long total_uncmp = 0;
 192    unsigned long int total_cmp = 0;
 193
 194    for (int i=0; i<cts; i++ ) {
 195
 196       if ( e_units[i] == 0 )
 197          continue;
 198
 199       total_uncmp += (e_units[i] -> word -> size()) * (e_units[i] -> freq);
 200       total_cmp += (e_units[i] -> bits) * (e_units[i] -> freq);
 201
 202       out << *(e_units[i] -> word) << ":" << e_units[i]->bits << "\n";
 203    }
 204    total_cmp = total_cmp / 8 + total_cmp % 8;
 205
 206 /*
 207    debug(cerr, total_uncmp);
 208    debug(cerr, total_cmp);
 209
 210    debug(cerr, 1 - float(total_cmp) / float(total_uncmp) );
 211 */
 212
 213    return out;
 214 }
 215
 216 // self modifying buf ptr after taking an encoding unit.
 217 encoding_unit* huff::get_e_unit(unsigned char*& buf, int len)
 218 {
 219    encoding_unit* x = tri -> parse(buf, len) ;
 220
 221 //debug(cerr, *(x -> word));
 222
 223    buf += x -> word -> size();
 224    return x;
 225 }
 226
 227 int total_uncomp = 0;
 228 int total_comp = 0;
 229
 230 void huff::compress(const buffer& uncompressed, buffer& compressed)
 231 {
 232 //debug(cerr, *(buffer*)&uncompressed);
 233    if ( compressed.buf_sz() < uncompressed.buf_sz() )
 234       compressed.expand_chunk(uncompressed.buf_sz());
 235
 236
 237    unsigned short total_bits = 0;
 238
 239    int uncmp_sz = uncompressed.content_sz();
 240    unsigned char* buf = (unsigned char*)uncompressed.get_base();
 241
 242
 243    unsigned int code_buf = 0;
 244    unsigned int rem_long = 0;
 245    int rem_bits = 0;
 246
 247    encoding_unit *e_ptr = 0;
 248
 249    while ( uncmp_sz > 0 ) {
 250
 251        //e_ptr = get_e_unit(buf, uncmp_sz);
 252
 253        e_ptr = tri -> parse(buf, uncmp_sz);
 254
 255        buf += e_ptr -> word -> size();
 256        uncmp_sz -= e_ptr -> word -> size();
 257
 258        if ( rem_bits + e_ptr -> bits > 32 ) {
 259
 260           code_buf = e_ptr -> code;          // shift bits to the higher end
 261
 262           rem_long <<= 32-rem_bits;
 263
 264           rem_bits += e_ptr -> bits - 32;    // new rem_bits
 265
 266           code_buf >>= rem_bits;             // get padding part
 267
 268           rem_long |= code_buf;              // padding
 269
 270           compressed.put( rem_long );
 271
 272 // save remaining (rem_bits + e_ptr -> bits - 32)  bits to rem_bits.
 273
 274           rem_long = e_ptr -> code & (~0L >> (32 - rem_bits));
 275
 276        } else {
 277           rem_long <<= e_ptr -> bits;
 278           rem_long |=  e_ptr -> code;
 279           rem_bits +=  e_ptr -> bits;
 280 //debug(cerr, hex(rem_long));
 281        }
 282
 283        total_bits += e_ptr -> bits;
 284        total_bits &= 0x1f; // take the mod on 32
 285    }
 286
 287    if ( rem_bits > 0 ) {
 288       rem_long <<= 32 - rem_bits;
 289 //MESSAGE(cerr, "PUT");
 290 //debug(cerr, hex(rem_long));
 291       compressed.put( rem_long );
 292    }
 293
 294 //debug(cerr, total_bits);
 295    compressed.put(char(total_bits));
 296
 297 //   total_uncomp += uncompressed.content_sz();
 298 //   total_comp += compressed.content_sz();
 299
 300 /*
 301    debug(cerr, total_uncomp);
 302    debug(cerr, total_comp);
 303
 304    debug(cerr,
 305          1-float(compressed.content_sz()-1)/float(uncompressed.content_sz())
 306         );
 307 */
 308 }
 309
 310 void huff::decompress(buffer& compressed, buffer& uncompressed)
 311 {
 312    char* buf_base = uncompressed.get_base();
 313    char* str;
 314    int str_len;
 315
 316    char rem_bits;
 317
 318    int ct = (compressed.content_sz() - 1) >> 2;
 319
 320    unsigned int c;
 321
 322    int bits_bound = 32;
 323
 324    htr_node *node_ptr = htr_root;
 325
 326    do {
 327       compressed.get(c); ct--;
 328
 329       if ( ct == 0 ) {
 330          compressed.get(rem_bits);
 331 //debug(cerr, int(rem_bits));
 332          bits_bound = rem_bits ;
 333       }
 334
 335       for ( int i=0;i<bits_bound; i++ ) {
 336          if ( node_ptr -> left == 0 && node_ptr -> right == 0 ) {
 337 //for ( int j=0; j<node_ptr -> eu -> word -> size(); j++ ) {
 338 // cerr << (node_ptr -> eu -> word -> get())[j];
 339 //}
 340
 341             str_len = node_ptr -> eu -> word -> size();
 342             str = node_ptr -> eu -> word -> get();
 343
 344             if ( str_len == 1 ) {
 345
 346                 *buf_base = str[0];
 347                 buf_base++;
 348
 349 //                uncompressed.put((node_ptr -> eu -> word -> get())[0]);
 350             } else {
 351
 352
 353                 memcpy(buf_base, str, str_len);
 354                 buf_base += str_len;
 355
 356
 357 /*
 358                 uncompressed.put( node_ptr -> eu -> word -> get(),
 359                                   node_ptr -> eu -> word -> size()
 360                                 );
 361 */
 362
 363             }
 364             node_ptr = htr_root;
 365          }
 366
 367          if ( c & 0x80000000 )
 368             node_ptr = node_ptr -> left;
 369          else
 370             node_ptr = node_ptr -> right;
 371
 372          c <<= 1;
 373       }
 374
 375
 376    } while ( ct>0 );
 377
 378 //debug(cerr, buf_base-uncompressed.get_base());
 379    uncompressed.set_content_sz(buf_base-uncompressed.get_base());
 380
 381    if ( rem_bits > 0 )
 382       uncompressed.put( node_ptr -> eu -> word -> get(),
 383                         node_ptr -> eu -> word -> size()
 384                       );
 385 }
 386
 387 //////////////////////////////////////////////////////////
 388 //
 389 //////////////////////////////////////////////////////////
 390
 391 MMDB_BODIES(huff)
 392
 393 int huff::cdr_sizeof()
 394 {
 395    return pstring::cdr_sizeof();
 396 }
 397
 398 io_status huff::cdrOut(buffer& buf)
 399 {
 400 //MESSAGE(cerr, "huff::cdrOut");
 401 //debug(cerr, my_oid());
 402    static buffer v_out_buf(LBUFSIZ);
 403
 404    if ( cts > 0 ) {
 405 //MESSAGE(cerr, "huff::cdrOut: dict out");
 406       int sz = sizeof(int);
 407       for ( int i=0; i<cts; i++ ) {
 408          sz += ( e_units[i] -> word -> size() +
 409                         sizeof(unsigned int) +
 410                         sizeof(char)
 411                       );
 412       }
 413
 414       v_out_buf.expand_chunk(sz);
 415
 416       v_out_buf.put(cts);
 417
 418       int word_sz;
 419
 420       for ( i=0; i<cts; i++ ) {
 421          word_sz = e_units[i] -> word -> size();
 422          v_out_buf.put(char(word_sz));
 423
 424          v_out_buf.put(e_units[i] -> word -> get(), word_sz);
 425          v_out_buf.put(e_units[i] -> freq);
 426       }
 427
 428       pstring::update(v_out_buf.get_base(), v_out_buf.content_sz());
 429    }
 430
 431    return pstring::cdrOut(buf);
 432 }
 433
 434 // format:
 435 //     entries_int
 436 //     (len_byte word_chars freq_int)+
 437 //
 438 io_status huff::cdrIn(buffer& buf)
 439 {
 440    static buffer v_in_buf(0);
 441
 442    pstring::cdrIn(buf);
 443
 444    if ( pstring::size() > 0 ) {
 445
 446       v_in_buf.set_chunk(pstring::get(), pstring::size());
 447       v_in_buf.set_content_sz(pstring::size());
 448
 449       v_in_buf.get(cts);
 450
 451       char word_buf[BUFSIZ];
 452       char word_sz;
 453       unsigned int word_freq;
 454       //ostring *z = 0;
 455
 456       for ( int i=0; i<cts; i++ ) {
 457
 458          v_in_buf.get(word_sz);
 459          v_in_buf.get(word_buf, int(word_sz));
 460          v_in_buf.get(word_freq);
 461
 462 /*
 463          z = new ostring((char*)word_buf, word_sz);
 464          extend_alphabet();
 465          alphabet[alphabet_sz++] = new encoding_unit(z, word_freq);
 466 */
 467
 468          tri -> add_to_alphabet((unsigned char*)word_buf, word_sz, word_freq);
 469       }
 470
 471    e_units = tri -> get_alphabet(cts);
 472
 473    build_tree();
 474    calculate_code();
 475    delete tri; tri = 0;
 476
 477 //print_alphabet(cerr);
 478
 479    }
 480
 481    return done;
 482 }
 483
 484 trie* alphabet = 0;
 485
 486 void trie_add_wrap(unsigned char* buf, int len, int action_num)
 487 {
 488    switch ( action_num ) {
 489       case 1:
 490          alphabet -> add(buf, len);
 491          break;
 492       case 2:
 493          alphabet -> add_letters(buf, len);
 494          break;
 495
 496       default:
 497          debug(cerr, action_num);
 498          throw(stringException("unknown action number"));
 499    }
 500 }
 501
 502
 503 io_status huff::build_dict(lex_func_t f_lex, getchar_func_t f_getchar)
 504 {
 505 MESSAGE(cerr, "get to huff build dict");
 506    fill_buf_func = f_getchar;
 507
 508    alphabet = tri;
 509
 510    lex_action_func = trie_add_wrap;
 511
 512    if ( (*f_lex)() != 0 )
 513       throw(stringException("huff::asciiIn(): Parsing input failed"));
 514
 515    e_units = tri -> get_alphabet(cts);
 516
 517 //debug(cerr, *tri);
 518
 519    build_tree();
 520    calculate_code();
 521
 522 //print_alphabet(cerr);
 523
 524    set_mode(UPDATE, true);
 525
 526    return done;
 527 }
 528