Subversion Repositories pentevo

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #include "mhmt-types.h"
  5. #include "mhmt-globals.h"
  6. #include "mhmt-tb.h"
  7.  
  8. // entry for twobyters search and add
  9. struct tb_chain * tb_entry[65536];
  10.  
  11. struct tb_chain * tb_free; // linked list of freed tb_chain entries - NULL at the beginning
  12.  
  13. struct tb_bunch * tb_bunches; // all allocated bunches as linked list
  14.  
  15.  
  16.  
  17.  
  18. void init_tb(void)
  19. {
  20.         ULONG i;
  21.  
  22.         tb_free=NULL;    // init linked list of free tb_chain elements
  23.         tb_bunches=NULL; // no bunches already allocated
  24.  
  25.         for(i=0;i<65536;i++) // init array of 2-byte match pointers
  26.         {
  27.                 tb_entry[i]=NULL;
  28.         }
  29. }
  30.  
  31.  
  32. void free_tb(void)
  33. {
  34.         // free all allocated bunches
  35.  
  36.         struct tb_bunch * tbtmp;
  37.  
  38.         while( tb_bunches )
  39.         {
  40.                 tbtmp=tb_bunches;
  41.                 tb_bunches=tb_bunches->next;
  42.                 free( tbtmp );
  43.         }
  44. }
  45.  
  46. // addw new twobyter:
  47. // index=(prev<<8)+curr - index into tb_entry,
  48. // position - position in input file for 'curr' byte
  49. // returns zero if any error (cant allocate mem), otherwise 1
  50. ULONG add_tb(UWORD index, OFFSET position)
  51. {
  52.         struct tb_chain * newtb;
  53.  
  54.         newtb=get_free_tb();
  55.         if( !newtb )
  56.         { // no free elements
  57.  
  58.                 if( (OFFSET)(position+wrk.prelen) > (OFFSET)wrk.maxwin ) // if there could be enough tbs to try to flush
  59.                 {
  60.                         // try to flush current chain
  61.                         cutoff_tb_chain(index,position);
  62.                 }
  63.  
  64.                 newtb=get_free_tb();
  65.                 if( !newtb )
  66.                 { // nothing free - allocate new bunch
  67.                         if( !add_bunch_of_tb() )
  68.                         {
  69.                                 return 0;
  70.                         }
  71.  
  72.                         newtb=get_free_tb(); // here is no chance to fail!... hopefully...
  73.                 }
  74.  
  75.         }
  76.  
  77.  
  78.  
  79.         newtb->pos=position-1; // points to the first byte of given two bytes
  80.         newtb->next=tb_entry[index];
  81.         tb_entry[index]=newtb;
  82.  
  83.  
  84.         return 1;
  85. }
  86.  
  87.  
  88. // shorten given twobyter chain to have only actual (<wrk.maxwin old) elements, giving some free elements to reuse
  89. void cutoff_tb_chain(UWORD index,OFFSET position)
  90. {
  91.         struct tb_chain * curr, * prev;
  92.  
  93.  
  94.         curr=tb_entry[index];
  95.         if( !curr ) return; // if nothing to remove
  96.  
  97.  
  98.         // see if we should delete some elements after first element in the given chain
  99.         prev=curr;
  100.         curr=curr->next;
  101.  
  102.         while( curr )
  103.         {
  104.                 if( (position-(curr->pos)) > (OFFSET)wrk.maxwin ) // found some old element: delete rest of chain along with it
  105.                 {
  106.                         // find end of chain
  107.                         while( curr->next )
  108.                         {
  109.                                 curr = curr->next;
  110.                         }
  111.  
  112.                         // now curr - last chain element, prev->next - beginning of orphaned chain
  113.                         // add orphaned chain to free list
  114.                         curr->next = tb_free;
  115.                         tb_free = prev->next;
  116.  
  117.                         prev->next = NULL; // cut off chain
  118.  
  119.                         break;
  120.                 }
  121.                 else
  122.                 {
  123.                         prev=curr;
  124.                         curr=curr->next;
  125.                 }
  126.         }
  127.  
  128.         // delete first (entry) element in chain if needed (in this case, all subsequent els are already deleted)
  129.         curr=tb_entry[index];
  130.         if( (position-(curr->pos)) > (OFFSET)wrk.maxwin )
  131.         {
  132.                 tb_entry[index] = NULL;
  133.  
  134.                 curr->next=tb_free; // element goes to free list
  135.                 tb_free=curr;
  136.         }
  137. }
  138.  
  139.  
  140. // adds new bunch of TBs when needed
  141. // zero - error
  142. ULONG add_bunch_of_tb(void)
  143. {
  144.         ULONG i;
  145.         struct tb_bunch * newbunch;
  146.  
  147.         // alloc new bunch
  148.         newbunch=(struct tb_bunch *)malloc( sizeof(struct tb_bunch) );
  149.         if( !newbunch ) return 0;
  150.  
  151.         // link every twobyter into one list
  152.         for(i=0;i<(BUNCHSIZE-1);i++)
  153.         {
  154.                 newbunch->bunch[i].next=&(newbunch->bunch[i+1]);
  155.         }
  156.  
  157.         // add this list to the free list
  158.         newbunch->bunch[BUNCHSIZE-1].next=tb_free;
  159.         tb_free=&(newbunch->bunch[0]);
  160.  
  161.         // add bunch to bunches list
  162.         newbunch->next=tb_bunches;
  163.         tb_bunches=newbunch;
  164.  
  165.         return 1;
  166. }
  167.  
  168.  
  169. // find free tb, if any, otherwise NULL
  170. struct tb_chain * get_free_tb(void)
  171. {
  172.         struct tb_chain * newtb;
  173.  
  174.         if( tb_free )
  175.         {
  176.                 newtb=tb_free;
  177.                 tb_free=tb_free->next;
  178.  
  179.                 return newtb;
  180.         }
  181.         else
  182.         {
  183.                 return NULL;
  184.         }
  185. }
  186.  
  187.