EnglishРусский  

   ..

   delzge.c

   enlzge.c

   lzge.c

   lzge.h

   match.c

   match.h

Реклама

Инсталлятор CreateInstall
Бесплатные и коммерческие инсталляторы

  1 /******************************************************************************
  2 *
  3 * Copyright (C) 2009, The Gentee Group. All rights reserved. 
  4 * This file is part of the Gentee open source project - http://www.gentee.com. 
  5 * 
  6 * THIS FILE IS PROVIDED UNDER THE TERMS OF THE GENTEE LICENSE ("AGREEMENT"). 
  7 * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS FILE CONSTITUTES RECIPIENTS 
  8 * ACCEPTANCE OF THE AGREEMENT.
  9 *
 10 * Author: Alexey Krivonogov ( gentee )
 11 *
 12 ******************************************************************************/
 13 
 14 #include "match.h"
 15 #include "lzge.h"
 16 //#include "K:\Gentee\Gentee Language\VM Lib\memory.h"
 17 
 18 //--------------------------------------------------------------------------
 19 
 20 dword STDCALL match_new( psmatch match, pbyte start, pbyte end, dword level )
 21 {
 22    dword  i;
 23    dword  hsize[] = { 16, 16, 19 };
 24    dword  wsize[] = { 15, 16, 15 };
 25 
 26    match->hash2 = ( pdword )mem_allocz( ( 1 << 16 ) * sizeof( dword ));
 27 
 28    wsize[2] = min( 21, lzge_bits( end - start ));
 29 
 30    for ( i = 0; i < 3; i++ )
 31    {
 32       if ( i == 1 && wsize[ 1 ] > wsize[2] ) break;
 33       if ( i == 2 && wsize[ 1 ] == wsize[2] ) break;
 34 
 35       match->hash[ i ] = ( pdword )mem_allocz( ( 1 << hsize[ i ] ) * sizeof( dword ));
 36       match->hsize[ i ] = 1 << hsize[i];
 37       match->next[ i ] = ( pdword )mem_alloc( ( 1 << wsize[i] ) * sizeof( dword ));
 38       match->size[ i ] = 1 << wsize[i];
 39       match->top[ i ] = 0;
 40       match->limit[i] = ( 1 << min( 14, level + 3 + 21 - wsize[2] ));
 41    }
 42    match->count = i;
 43 //   printf("Count=%i size=%i\n", match->count, 1<< wsize[2] );
 44    match->start = start;
 45    match->end = end;
 46 
 47    return ( 1 << wsize[2] ) - 1;
 48 }
 49 
 50 //--------------------------------------------------------------------------
 51 
 52 void STDCALL match_destroy( psmatch match )
 53 {
 54    dword  i;
 55 
 56    mem_free( match->hash2 );
 57    for ( i = 0; i < match->count; i++ )
 58    {
 59       mem_free( match->hash[i] );
 60       mem_free( match->next[i] );
 61    }
 62 }
 63 
 64 //--------------------------------------------------------------------------
 65 
 66 dword STACKAPI match_find( psmatch match, pbyte input, pdword retoff )
 67 // Вызов должен быть со второго символа
 68 {
 69    dword  off = input - match->start;
 70    dword  hash;
 71    dword  len = 1;
 72    dword  lastoff; // Последнее найденное смещение
 73    dword  i, limit;
 74    dword  cur, offset;
 75    uint   k;//, j;
 76 
 77    if ( !off || input + 2 > match->end ) return len;
 78 
 79    *retoff = 0;
 80 // Ищем по длине 2
 81    if ( cur = match->hash2[ *( pword )input ] )
 82    {
 83       offset = off - cur + 1;
 84       if ( offset < 256 + MIN_OFFSET )
 85       {
 86          len = 2;
 87          while ( input[ len ] == *( input - offset + len ) && 
 88             input + len < match->end )
 89             len++;
 90          *retoff = offset;
 91       }
 92    }
 93    hash = ((( dword )input[0] ) << 3 ) ^ input[ 1 ];
 94 // Ищем по остальным длинам
 95    for ( i = 0; i < match->count; i++ )
 96    {
 97 //      if ( input + 3 + i > match->end ) break;
 98       if ( input + len == match->end ||
 99            input + 3 + i > match->end )
100          break;
101 
102       limit = 0;
103       hash = ( hash << 3 ) ^ input[ 2 + i ];
104       hash &= match->hsize[i] - 1;
105       lastoff = 0;
106       cur = match->hash[ i ][ hash ];
107 
108       while ( cur-- )
109       {
110          // Находим смещение
111          offset = match->top[i] + ( cur < match->top[i] ? 0 : match->size[i] ) - 
112                                   cur + 2 + i;
113          if ( offset <= lastoff || offset >= match->size[i] ) break;
114          lastoff = offset;
115          if ( offset <= *retoff ) goto next;
116 
117          if ( len > 2 + i )  // Уже есть найденные вхождения
118          {
119             for ( k = len; k >= 0; k-- )
120             {
121                if ( input[ k ] != *( input - offset + k ))
122                   goto next;
123             }
124             len++;
125          }
126          else
127          {
128             for ( k = 0; k < 3 + i; k++ )
129             {
130                if ( input[ k ] != *( input - offset + k ))
131                   goto next;
132             }
133             len = 3 + i;
134          }
135          // Теперь смотрим вправо
136          while ( input[ len ] == *( input - offset + len ) && input + len < match->end )
137             len++;
138          *retoff = offset;
139 next:
140          cur = match->next[i][ cur ];
141          if ( ++limit > match->limit[ i ] || input + len == match->end )
142             break;
143       }
144    }
145    if ( len >= match->size[ match->count - 1 ] - 1 )
146       len = match->size[ match->count - 1 ] - 1;
147 //   if ( input + len > match->end )
148 //      printf("Error off=%i len=%i\n ", *retoff, len );
149 // Обновляем хэш-таблицы
150    k = len;
151    while ( k )
152    {
153       match_update( match, input );
154 
155 /*      match->hash2[ *( pword )( input - 2 ) ] = input - match->start - 1;
156    
157 // Ищем по остальным длинам
158       for ( i = 0; i < match->count; i++ )
159       {  
160          if ( input - match->start < i + 2 ) break;
161          hash = *( input - 2 - i );
162          for ( j = 1 + i; j >= 0; j-- )
163             hash = ( hash << 3 ) ^ *( input - j );
164          hash &= match->hsize[i] - 1;
165 
166          match->next[i][ match->top[i]] = match->hash[ i ][ hash ];
167          match->hash[i][ hash ] = match->top[i] + 1;
168          match->top[i]++;
169          if ( match->top[i] == match->size[i] )
170             match->top[i] = 0;
171       }*/
172       k--;
173       input++;
174    }
175    return len;
176 }
177 
178 //--------------------------------------------------------------------------
179 
180 dword  STACKAPI match_update( psmatch match, pbyte input )
181 {
182    dword  i;
183    int    j;
184    dword  hash;
185 
186 //   if ( input == match->start ) return 1;
187 
188    match->hash2[ *( pword )( input - 2 ) ] = input - match->start - 1;
189    
190 // Ищем по остальным длинам
191    for ( i = 0; i < match->count; i++ )
192    {  
193       if ( input - match->start < (int)( i + 2 )) break;
194       hash = *( input - 2 - i );
195       for ( j = 1 + i; j >= 0; j-- )
196          hash = ( hash << 3 ) ^ *( input - j );
197       hash &= match->hsize[i] - 1;
198 
199       match->next[i][ match->top[i]] = match->hash[ i ][ hash ];
200       match->hash[i][ hash ] = match->top[i] + 1;
201       match->top[i]++;
202 
203       if ( match->top[i] == match->size[i] )
204          match->top[i] = 0;
205    }
206    return 1;
207 }
208 
209 //--------------------------------------------------------------------------
210 
Редактировать