diff options
author | Magnus Lundborg <lundborg.magnus@gmail.com> | 2013-10-21 07:31:05 (GMT) |
---|---|---|
committer | Magnus Lundborg <lundborg.magnus@gmail.com> | 2013-10-21 07:31:05 (GMT) |
commit | beaa92cb293a4147aef8ed03027500804535ed96 (patch) | |
tree | c8427746983418476a99b5c61847e0b4eeca5f1d /src/compression/lz77.c | |
parent | 885f2782f9f48b69bc229612b0734b4de48b890b (diff) |
Fixed compiler warnings and linking errors in MSVC.
Changed tabs to spaces in tng_compression functions.
Diffstat (limited to 'src/compression/lz77.c')
-rw-r--r-- | src/compression/lz77.c | 386 |
1 files changed, 193 insertions, 193 deletions
diff --git a/src/compression/lz77.c b/src/compression/lz77.c index 5ea63cf..dba6400 100644 --- a/src/compression/lz77.c +++ b/src/compression/lz77.c @@ -32,7 +32,7 @@ The second value is the "inverse" of the first value and can be used to find the locations of similar strings. */ static void sort_strings(unsigned int *vals, int nvals, - unsigned int *output) + unsigned int *output) { int i; int *indices=warnmalloc(2*nvals*sizeof *indices); @@ -55,79 +55,79 @@ static void sort_strings(unsigned int *vals, int nvals, for (i=0; i<nvals; i++) { /* If we have not already found a repeating string we must find - it. */ + it. */ if (!nrepeat[i]) - { - int maxrepeat=nvals*2; - int j,k,m; - int good_j=-1, good_k=0; - int kmax=16; - /* Track repeating patterns. - k=1 corresponds to AAAAA... - k=2 corresponds to ABABAB... - k=3 corresponds to ABCABCABCABC... - k=4 corresponds to ABCDABCDABCD... - etc. */ - for (k=kmax; k>=1; k--) - { - try_next_k: - if (k>=1) - { - for (j=k; j<maxrepeat; j+=k) - { - int is_equal=1; - for (m=0; m<k; m++) - if (vals[(i+m)%nvals]!=vals[(i+j+m)%nvals]) - { - is_equal=0; - break; - } - if (is_equal) - { - int new_j=j+k; - if (new_j>maxrepeat) - new_j=j; - if ((new_j>good_j) || ((new_j==good_j) && (k<good_k))) - { - good_j=new_j; /* We have found that - the strings repeat - for this length... */ - good_k=k; /* ...and with this - length of the - repeating - pattern. */ - } - } - else - { - /* We know that it is no point in trying - with more than m */ - if (j==0) - { - k=m; - } - else - k--; - goto try_next_k; - } - } - } - } - /* From good_j and good_k we know the repeat for a large - number of strings. The very last repeat length should not - be assigned, since it can be much longer if a new test is - done. */ - for (m=0; (m+good_k<good_j) && (i+m<nvals); m+=good_k) - { - int repeat=good_j-m; - if (repeat>nvals) - repeat=nvals; - nrepeat[i+m]=((unsigned int) (good_k)) | (((unsigned int) (repeat))<<8); - } - /* If no repetition was found for this value signal that here. */ - if (!nrepeat[i]) - nrepeat[i+m]=257U; /* This is 1<<8 | 1 */ - } + { + int maxrepeat=nvals*2; + int j,k,m; + int good_j=-1, good_k=0; + int kmax=16; + /* Track repeating patterns. + k=1 corresponds to AAAAA... + k=2 corresponds to ABABAB... + k=3 corresponds to ABCABCABCABC... + k=4 corresponds to ABCDABCDABCD... + etc. */ + for (k=kmax; k>=1; k--) + { + try_next_k: + if (k>=1) + { + for (j=k; j<maxrepeat; j+=k) + { + int is_equal=1; + for (m=0; m<k; m++) + if (vals[(i+m)%nvals]!=vals[(i+j+m)%nvals]) + { + is_equal=0; + break; + } + if (is_equal) + { + int new_j=j+k; + if (new_j>maxrepeat) + new_j=j; + if ((new_j>good_j) || ((new_j==good_j) && (k<good_k))) + { + good_j=new_j; /* We have found that + the strings repeat + for this length... */ + good_k=k; /* ...and with this + length of the + repeating + pattern. */ + } + } + else + { + /* We know that it is no point in trying + with more than m */ + if (j==0) + { + k=m; + } + else + k--; + goto try_next_k; + } + } + } + } + /* From good_j and good_k we know the repeat for a large + number of strings. The very last repeat length should not + be assigned, since it can be much longer if a new test is + done. */ + for (m=0; (m+good_k<good_j) && (i+m<nvals); m+=good_k) + { + int repeat=good_j-m; + if (repeat>nvals) + repeat=nvals; + nrepeat[i+m]=((unsigned int) (good_k)) | (((unsigned int) (repeat))<<8); + } + /* If no repetition was found for this value signal that here. */ + if (!nrepeat[i]) + nrepeat[i+m]=257U; /* This is 1<<8 | 1 */ + } } /* Sort cyclic shift matrix. */ @@ -155,19 +155,19 @@ static void add_circular(int *previous,int v, int i) { previous[(NUM_PREVIOUS+3)*v]++; if (previous[(NUM_PREVIOUS+3)*v]>NUM_PREVIOUS) - previous[(NUM_PREVIOUS+3)*v]=NUM_PREVIOUS; + previous[(NUM_PREVIOUS+3)*v]=NUM_PREVIOUS; previous[(NUM_PREVIOUS+3)*v+3+previous[(NUM_PREVIOUS+3)*v+1]]=i; previous[(NUM_PREVIOUS+3)*v+1]++; if (previous[(NUM_PREVIOUS+3)*v+1]>=NUM_PREVIOUS) - previous[(NUM_PREVIOUS+3)*v+1]=0; + previous[(NUM_PREVIOUS+3)*v+1]=0; } previous[(NUM_PREVIOUS+3)*v+2]=i; } void Ptngc_comp_to_lz77(unsigned int *vals, int nvals, - unsigned int *data, int *ndata, - unsigned int *len, int *nlens, - unsigned int *offsets, int *noffsets) + unsigned int *data, int *ndata, + unsigned int *len, int *nlens, + unsigned int *offsets, int *noffsets) { int noff=0; int ndat=0; @@ -192,112 +192,112 @@ void Ptngc_comp_to_lz77(unsigned int *vals, int nvals, #endif int firstoffset=i-MAX_OFFSET; if (firstoffset<0) - firstoffset=0; + firstoffset=0; if (i!=0) - { - int largest_len=0; - int largest_offset=0; - int icirc, ncirc; - /* Is this identical to a previous offset? Prefer close - values for offset. Search through circular buffer for the - possible values for the start of this string. */ - ncirc=previous[(NUM_PREVIOUS+3)*vals[i]]; - for (icirc=0; icirc<ncirc; icirc++) - { - int iptr=previous[(NUM_PREVIOUS+3)*vals[i]+1]-icirc-1; - if (iptr<0) - iptr+=NUM_PREVIOUS; - j=previous[(NUM_PREVIOUS+3)*vals[i]+3+iptr]; - if (j<firstoffset) - break; + { + int largest_len=0; + int largest_offset=0; + int icirc, ncirc; + /* Is this identical to a previous offset? Prefer close + values for offset. Search through circular buffer for the + possible values for the start of this string. */ + ncirc=previous[(NUM_PREVIOUS+3)*vals[i]]; + for (icirc=0; icirc<ncirc; icirc++) + { + int iptr=previous[(NUM_PREVIOUS+3)*vals[i]+1]-icirc-1; + if (iptr<0) + iptr+=NUM_PREVIOUS; + j=previous[(NUM_PREVIOUS+3)*vals[i]+3+iptr]; + if (j<firstoffset) + break; #if 0 - fprintf(stderr,"Starting search for %d at %d. Found %d\n",vals[i],j,vals[j]); + fprintf(stderr,"Starting search for %d at %d. Found %d\n",vals[i],j,vals[j]); #endif - while ((j<i) && (vals[j]==vals[i])) - { - if (j>=firstoffset) - { - for (k=0; i+k<nvals; k++) - if (vals[j+k]!=vals[i+k]) - break; - if ((k>largest_len) && ((k>=(i-j)+16) || ((k>4) && (i-j==1)))) - { - largest_len=k; - largest_offset=j; - } - } - j++; - } - } + while ((j<i) && (vals[j]==vals[i])) + { + if (j>=firstoffset) + { + for (k=0; i+k<nvals; k++) + if (vals[j+k]!=vals[i+k]) + break; + if ((k>largest_len) && ((k>=(i-j)+16) || ((k>4) && (i-j==1)))) + { + largest_len=k; + largest_offset=j; + } + } + j++; + } + } #if 0 - /* Search in sorted string buffer too. */ - kmin=info[i*2+1]-MAX_STRING_SEARCH; - kmax=info[i*2+1]+MAX_STRING_SEARCH; - if (kmin<0) - kmin=0; - if (kmax>=nvals) - kmax=nvals; - for (k=kmin; k<kmax; k++) - { - int m; - int s=info[k*2]; - if ((s<i) && (s+MAX_OFFSET>=i)) - { - for (m=0; i+m<nvals; m++) - if (vals[i+m]!=vals[(s+m)%nvals]) - break; - if ((m>largest_len) && (m>4) && (m+2>=(i-s))) - { - largest_len=m; - largest_offset=s; + /* Search in sorted string buffer too. */ + kmin=info[i*2+1]-MAX_STRING_SEARCH; + kmax=info[i*2+1]+MAX_STRING_SEARCH; + if (kmin<0) + kmin=0; + if (kmax>=nvals) + kmax=nvals; + for (k=kmin; k<kmax; k++) + { + int m; + int s=info[k*2]; + if ((s<i) && (s+MAX_OFFSET>=i)) + { + for (m=0; i+m<nvals; m++) + if (vals[i+m]!=vals[(s+m)%nvals]) + break; + if ((m>largest_len) && (m>4) && (m+2>=(i-s))) + { + largest_len=m; + largest_offset=s; #if 0 - fprintf(stderr,"Offset: %d %d\n",m,i-s); + fprintf(stderr,"Offset: %d %d\n",m,i-s); #endif - } - } - } + } + } + } #endif - /* Check how to write this info. */ - if (largest_len>MAX_LEN) - largest_len=MAX_LEN; - if (largest_len) - { - if (i-largest_offset==1) - { - data[ndat++]=0; - } - else - { - data[ndat++]=1; - offsets[noff++]=i-largest_offset; - } - len[nlen++]=largest_len; + /* Check how to write this info. */ + if (largest_len>MAX_LEN) + largest_len=MAX_LEN; + if (largest_len) + { + if (i-largest_offset==1) + { + data[ndat++]=0; + } + else + { + data[ndat++]=1; + offsets[noff++]=i-largest_offset; + } + len[nlen++]=largest_len; #if 0 - fprintf(stderr,"l:o: %d:%d data=%d i=%d\n",largest_len,i-largest_offset,ndat,i); - fflush(stderr); + fprintf(stderr,"l:o: %d:%d data=%d i=%d\n",largest_len,i-largest_offset,ndat,i); + fflush(stderr); #endif #if 0 - fprintf(stderr,"Found largest len %d at %d.\n",largest_len,i-largest_offset); + fprintf(stderr,"Found largest len %d at %d.\n",largest_len,i-largest_offset); #endif - /* Add these values to the circular buffer. */ - for (k=0; k<largest_len; k++) - add_circular(previous,vals[i+k],i+k); - i+=largest_len-1; - } - else - { - data[ndat++]=vals[i]+2; - /* Add this value to circular buffer. */ - add_circular(previous,vals[i],i); - } - } + /* Add these values to the circular buffer. */ + for (k=0; k<largest_len; k++) + add_circular(previous,vals[i+k],i+k); + i+=largest_len-1; + } + else + { + data[ndat++]=vals[i]+2; + /* Add this value to circular buffer. */ + add_circular(previous,vals[i],i); + } + } else - { - data[ndat++]=vals[i]+2; - /* Add this value to circular buffer. */ - add_circular(previous,vals[i],i); - } + { + data[ndat++]=vals[i]+2; + /* Add this value to circular buffer. */ + add_circular(previous,vals[i],i); + } } *noffsets=noff; *ndata=ndat; @@ -309,9 +309,9 @@ void Ptngc_comp_to_lz77(unsigned int *vals, int nvals, } void Ptngc_comp_from_lz77(unsigned int *data, int ndata, - unsigned int *len, int nlens, - unsigned int *offsets, int noffsets, - unsigned int *vals, int nvals) + unsigned int *len, int nlens, + unsigned int *offsets, int noffsets, + unsigned int *vals, int nvals) { int i=0; int joff=0; @@ -324,27 +324,27 @@ void Ptngc_comp_from_lz77(unsigned int *data, int ndata, { unsigned int v=data[jdat++]; if (v<2) - { - int offset=1; - int k; - int length=(int)len[jlen++]; + { + int offset=1; + int k; + int length=(int)len[jlen++]; #if 0 - fprintf(stderr,"len=%d off=%d i=%d\n",length,offset,i); + fprintf(stderr,"len=%d off=%d i=%d\n",length,offset,i); #endif - if (v==1) - offset=offsets[joff++]; - for (k=0; k<length; k++) - { - vals[i]=vals[i-offset]; - if (i>=nvals) - { - fprintf(stderr,"too many vals.\n"); - exit(EXIT_FAILURE); - } - i++; - } - } + if (v==1) + offset=offsets[joff++]; + for (k=0; k<length; k++) + { + vals[i]=vals[i-offset]; + if (i>=nvals) + { + fprintf(stderr,"too many vals.\n"); + exit(EXIT_FAILURE); + } + i++; + } + } else - vals[i++]=v-2; + vals[i++]=v-2; } } |