?login_element?

Subversion Repositories NedoOS

Rev

Blame | Last modification | View Log | Download

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #include "mhmt-types.h"
  5. #include "mhmt-optimal.h"
  6.  
  7.  
  8. // allocate place for optimal chain building amd initialize it
  9. struct optchain * make_optch(ULONG actual_len)
  10. {
  11.         struct optchain * optch;
  12.  
  13.         ULONG i;
  14.  
  15.         // we allocate length+1 because all codes at the end of input stream will point
  16.         // to the length+1 place. Also we'll start reversing from length+1 position in optch array
  17.         optch = (struct optchain *)malloc( (actual_len+1)*sizeof(struct optchain) );
  18.  
  19.         if( optch )
  20.         {
  21.                 optch[0].code.length = 1; // 1st byte is always copied 'as-is', however, this is just filler,
  22.                 optch[0].code.disp   = 0; // not accounted elsewhere
  23.  
  24.                 // init prices to absolute maximum for optimal chain build-up
  25.                 optch[0].price = 0;
  26.                 optch[1].price = 8;
  27.                 for(i=2;i<(actual_len+1);i++)
  28.                         optch[i].price = 0xFFFFFFFF;
  29.         }
  30.  
  31.         return optch;
  32. }
  33.  
  34. struct optch_hst ** make_optch_hst(ULONG actual_len)
  35. {
  36.         struct optch_hst ** optch_bunch;
  37.  
  38.         ULONG i,j;
  39.  
  40.  
  41.         optch_bunch = (struct optch_hst **)calloc( 8, sizeof(struct optch_hst *) );
  42.  
  43.         if( optch_bunch )
  44.         {
  45.                 for(i=0;i<8;i++)
  46.                 {
  47.                         optch_bunch[i] = (struct optch_hst *)malloc( (actual_len+1)*sizeof(struct optch_hst) );
  48.                         if( !optch_bunch[i] )
  49.                         { // error recovery (free allocated mem)
  50.                                 free_optch_hst(optch_bunch);
  51.                                 return NULL;
  52.                         }
  53.                 }
  54.  
  55.                 for(i=0;i<8;i++)
  56.                 {
  57.                         for(j=0;j<(actual_len+1);j++)
  58.                         {
  59.                                 optch_bunch[i][j].code.length = 0;
  60.                                 optch_bunch[i][j].code.disp   = 0;
  61.                                 optch_bunch[i][j].path        = (-1);
  62.                                 optch_bunch[i][j].price       = 0xFFFFFFFF;
  63.                         }
  64.                 }
  65.  
  66.                 optch_bunch[0][0].code.length = 1;
  67.                 optch_bunch[0][0].code.disp   = 0;
  68.  
  69.                 optch_bunch[0][0].price = 0;
  70.                 optch_bunch[0][1].price = 8;
  71.                
  72.                 optch_bunch[0][0].path = 0;
  73.                 optch_bunch[0][1].path = 0;
  74.         }
  75.  
  76.         return optch_bunch;
  77. }
  78.  
  79.  
  80.  
  81.  
  82. // free optchain array
  83. void free_optch(struct optchain * optch)
  84. {
  85.         if( optch )
  86.                 free( optch );
  87. }
  88.  
  89. void free_optch_hst(struct optch_hst ** optch)
  90. {
  91.         ULONG i;
  92.  
  93.         if( optch )
  94.         {
  95.                 for(i=0;i<8;i++)
  96.                 {
  97.                         if( optch[i] )
  98.                                 free( optch[i] );
  99.                 }
  100.                 free( optch );
  101.         }
  102. }
  103.  
  104.  
  105.  
  106.  
  107.  
  108. // update prices at the position given all lzcodes.
  109. // it also needs pointer to the function that calculates bit length of given LZ code
  110. void update_optch(ULONG position, struct lzcode * codes, ULONG (*get_lz_price)(OFFSET position, struct lzcode * lzcode), struct optchain * optch)
  111. {
  112.         ULONG codepos;
  113.         ULONG bitlen;
  114.         ULONG newpos;
  115.         LONG len;
  116.  
  117.         for( codepos = 0; len=codes[codepos].length; codepos++ ) // loop through all existing lz codes
  118.         {
  119.                 bitlen = (*get_lz_price)(position, &codes[codepos]); // get bit length of given lz code
  120.                 if( !bitlen )
  121.                 {
  122.                         printf("mhmt-optimal.c: update_optch() found zero bitlength of lz code. Fatal error.\n");
  123.                         exit(1);
  124.                 }
  125.                 else
  126.                 {
  127.                         if( len<0 ) len=(-len); // deal with negative lengths (special markers)
  128.  
  129.                         newpos = position + len; // look where current lz code points to and take from there old price reaching that location
  130.  
  131.                         if( optch[newpos].price > bitlen + optch[position].price ) // if oldprice is worse than with current lz code
  132.                         {
  133.                                 optch[newpos].price = bitlen + optch[position].price;
  134.                                 optch[newpos].code  = codes[codepos];
  135.                         }
  136.                 }
  137.         }
  138. }
  139.  
  140.  
  141.  
  142.  
  143.  
  144.  
  145. // reverses optimal chain making it ready for scanning (fetching optimal chain)
  146. //
  147. void reverse_optch(struct optchain * optch, ULONG actual_len)
  148. {
  149.         struct lzcode curr, temp;
  150.         ULONG position;
  151.         LONG len;
  152.  
  153.         position = actual_len;
  154.  
  155.         temp = optch[position].code;
  156.  
  157.         while(position>1)
  158.         {
  159.                 len = temp.length;
  160.                 if( len<0 ) len=(-len);
  161.  
  162.                 position -= len;
  163.  
  164.                 curr = temp;
  165.  
  166.                 temp = optch[position].code;
  167.                 optch[position].code = curr;
  168.         }
  169. }
  170.  
  171.  
  172.