« back to all changes in this revision
Viewing changes to encode.c
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Guillem Jover
- Date: 2004-06-27 08:07:09 UTC
- Revision ID: james.westby@ubuntu.com-20040627080709-1gkxm72ex66gkwe4
Tags: upstream-3.10.21
Import upstream version 3.10.21
- files added:
- cset2
- doc
- gnu
- highc
- msc6_os2
- resource
- resource/de
- resource/en
- resource/ge
- resource/ru
- settings
- vacpp
- wcc2_32
- win32
added
removed
encode.c
1
/*
2
* $Id: encode.c,v 1.7 2004/05/31 16:08:41 andrew_belov Exp $
3
* ---------------------------------------------------------------------------
4
* The data compression procedures are located in this module.
5
*
6
*/
7
8
#include "arj.h"
9
10
#ifdef TILED
11
#include <dos.h> /* Weird, eh? */
12
#endif
13
14
DEBUGHDR(__FILE__) /* Debug information block */
15
16
static int st_n;
17
18
unsigned short *c_freq;
19
unsigned short FAR *c_code;
20
unsigned short FAR *heap;
21
unsigned short len_cnt[17];
22
unsigned short p_freq[2*NP-1];
23
unsigned short pt_code[NPT];
24
int depth;
25
unsigned char FAR *buf;
26
unsigned char output_mask;
27
unsigned short output_pos;
28
int dicbit;
29
unsigned short t_freq[2*NT-1];
30
int heapsize;
31
unsigned short FAR *sortptr;
32
unsigned char *len;
33
unsigned short *freq;
34
unsigned short fpcount;
35
short FAR *fpbuf;
36
short FAR *dtree;
37
unsigned short treesize;
38
unsigned char *tree=NULL;
39
unsigned short numchars;
40
unsigned short dicsiz_cur;
41
unsigned short dicpos;
42
unsigned short tc_passes;
43
short FAR *ftree;
44
unsigned int dic_alloc;
45
unsigned long encoded_bytes;
46
47
/* Inline functions */
48
49
#define encode_c(c) \
50
putbits(c_len[c], c_code[c])
51
52
#define encode_p(p) \
53
{ \
54
unsigned int qc, q; \
55
qc=0; \
56
q=p; \
57
while(q) \
58
{ \
59
q>>=1; \
60
qc++; \
61
} \
62
putbits(pt_len[qc], pt_code[qc]); \
63
if(qc>1) \
64
putbits(qc-1, p); \
65
}
66
67
/* Bitwise output routine */
68
69
void putbits(int n_c, unsigned short n_x)
70
{
71
#ifdef ASM8086
72
asm{
73
mov cl, byte ptr n_c
74
mov dx, n_x
75
mov ch, cl
76
sub cl, 16
77
neg cl
78
shl dx, cl
79
mov cl, byte ptr bitcount
80
mov ax, dx
81
shr ax, cl
82
or bitbuf, ax
83
add cl, ch
84
cmp cl, 8
85
jge chunk1
86
mov byte ptr bitcount, cl
87
jmp procend
88
}
89
chunk1:
90
asm{
91
push si
92
mov si, out_bytes
93
cmp si, out_avail
94
jge flush
95
}
96
acc_loop:
97
asm{
98
mov bx, out_buffer
99
mov ah, byte ptr bitbuf+1
100
mov [bx+si], ah
101
inc si
102
sub cl, 8
103
cmp cl, 8
104
jge avail_chk
105
#if TARGET==OS2
106
shl bitbuf, 8
107
#else
108
mov ah, byte ptr bitbuf
109
mov al, 0
110
mov bitbuf, ax
111
#endif
112
jmp endpoint
113
}
114
avail_chk:
115
asm{
116
cmp si, out_avail
117
jge r_flush
118
}
119
cpoint:
120
asm{
121
mov al, byte ptr bitbuf
122
mov [bx+si], al
123
inc si
124
sub cl, 8
125
sub ch, cl
126
xchg cl, ch
127
shl dx, cl
128
mov bitbuf, dx
129
mov cl, ch
130
jmp endpoint
131
}
132
flush:
133
asm{
134
push dx
135
push cx
136
}
137
flush_compdata();
138
asm{
139
pop cx
140
pop dx
141
mov si, out_bytes
142
jmp short acc_loop
143
}
144
r_flush:
145
asm{
146
mov out_bytes, si
147
push dx
148
push cx
149
push bx
150
}
151
flush_compdata();
152
asm{
153
pop bx
154
pop cx
155
pop dx
156
mov si, out_bytes
157
jmp short cpoint
158
}
159
endpoint:
160
asm{
161
mov out_bytes, si
162
pop si
163
mov byte ptr bitcount, cl
164
}
165
procend:;
166
#else
167
int p_n;
168
int bt;
169
170
p_n=n_c;
171
n_c=16-n_c;
172
n_x<<=n_c;
173
n_c=bitcount;
174
bitbuf|=(n_x>>n_c);
175
n_c+=p_n;
176
if(n_c<8)
177
{
178
bitcount=n_c;
179
return;
180
}
181
bt=out_bytes;
182
if(bt>=out_avail)
183
{
184
flush_compdata();
185
bt=out_bytes;
186
}
187
out_buffer[bt++]=bitbuf>>8;
188
n_c-=8;
189
if(n_c<8)
190
{
191
bitbuf<<=8;
192
out_bytes=bt;
193
bitcount=n_c;
194
return;
195
}
196
if(bt>=out_avail)
197
{
198
out_bytes=bt;
199
flush_compdata();
200
bt=out_bytes;
201
}
202
out_buffer[bt++]=bitbuf;
203
n_c-=8;
204
p_n-=n_c;
205
bitbuf=n_x<<p_n;
206
out_bytes=bt;
207
bitcount=n_c;
208
#endif
209
}
210
211
/* Quick fill routine */
212
213
static void fill_fpbuf()
214
{
215
#ifdef ASM8086
216
asm{
217
push di
218
cld
219
mov ax, 65535
220
les di, fpbuf
221
mov cx, fpcount
222
rep stosw
223
pop di
224
}
225
#else
226
unsigned int i;
227
228
for(i=0; i<fpcount; i++)
229
fpbuf[i]=-1;
230
#endif
231
}
232
233
/* Reduces the number of bits for smaller files */
234
235
void adjust_dicbit()
236
{
237
if(uncompsize<16384)
238
dicbit=12;
239
}
240
241
/* Reads data from the source file or a memory region */
242
243
#if SFX_LEVEL>=ARJ
244
int fetch_uncomp(char *dest, int n)
245
{
246
unsigned int fetch_size;
247
248
if(file_packing)
249
return(fread_crc(dest, n, encstream));
250
else
251
{
252
if(encmem_remain==0)
253
return(0);
254
fetch_size=min((unsigned int)n, encmem_remain);
255
far_memmove((char FAR *)dest, encblock_ptr, fetch_size);
256
crc32_for_block(dest, fetch_size);
257
encmem_remain-=fetch_size;
258
encblock_ptr+=fetch_size;
259
return(fetch_size);
260
}
261
}
262
#endif
263
264
/* Fills the length table depending on the leaf depth (call with i==root) */
265
266
static void count_len(int i)
267
{
268
static int depth=0;
269
270
if(i<st_n)
271
len_cnt[(depth<16)?depth:16]++;
272
else
273
{
274
depth++;
275
count_len(left[i]);
276
count_len(right[i]);
277
depth--;
278
}
279
}
280
281
/* Makes length counter table */
282
283
static void NEAR make_len(int root)
284
{
285
int i, k;
286
unsigned short cum;
287
288
for(i=0; i<=16; i++)
289
len_cnt[i]=0;
290
count_len(root);
291
cum=0;
292
for(i=16; i>0; i--)
293
cum+=len_cnt[i]<<(16-i);
294
while(cum!=0)
295
{
296
if(debug_enabled&&strchr(debug_opt, 'f')!=NULL)
297
msg_cprintf(0, M_HDF_FIX);
298
len_cnt[16]--;
299
for(i=15; i>0; i--)
300
{
301
if(len_cnt[i]!=0)
302
{
303
len_cnt[i]--;
304
len_cnt[i+1]+=2;
305
break;
306
}
307
}
308
cum--;
309
}
310
for(i=16; i>0; i--)
311
{
312
k=len_cnt[i];
313
while(--k>=0)
314
len[*sortptr++]=i;
315
}
316
}
317
318
/* Sends i-th entry down the heap */
319
320
static void NEAR downheap(int i)
321
{
322
int j, k;
323
324
k=heap[i];
325
while((j=2*i)<=heapsize)
326
{
327
if(j<heapsize&&freq[heap[j]]>freq[heap[j+1]])
328
j++;
329
if(freq[k]<=freq[heap[j]])
330
break;
331
heap[i]=heap[j];
332
i=j;
333
}
334
heap[i]=k;
335
}
336
337
/* Encodes a length table element */
338
339
static void NEAR make_code(int n, unsigned char *len, unsigned short FAR *code)
340
{
341
int i;
342
unsigned short start[18];
343
344
start[1]=0;
345
for(i=1; i<=16; i++)
346
start[i+1]=(start[i]+len_cnt[i])<<1;
347
for(i=0; i<n; i++)
348
code[i]=start[len[i]]++;
349
}
350
351
/* Makes tree, calculates len[], returns root */
352
353
static int make_tree(int nparm, unsigned short *freqparm, unsigned char *lenparm, unsigned short FAR *codeparm)
354
{
355
int i, j, k, avail;
356
357
st_n=nparm;
358
freq=freqparm;
359
len=lenparm;
360
avail=st_n;
361
heapsize=0;
362
heap[1]=0;
363
for(i=0; i<st_n; i++)
364
{
365
len[i]=0;
366
if(freq[i]!=0)
367
heap[++heapsize]=i;
368
}
369
if(heapsize<2)
370
{
371
codeparm[heap[1]]=0;
372
return(heap[1]);
373
}
374
for(i=heapsize>>1; i>=1; i--)
375
downheap(i); /* Make priority queue */
376
sortptr=codeparm;
377
/* While queue has at least two entries */
378
do
379
{
380
i=heap[1]; /* Take out least-freq entry */
381
if(i<st_n)
382
*(sortptr++)=i;
383
heap[1]=heap[heapsize--];
384
downheap(1);
385
j=heap[1]; /* Next least-freq entry */
386
if(j<st_n)
387
*(sortptr++)=j;
388
k=avail++; /* Generate new node */
389
freq[k]=freq[i]+freq[j];
390
heap[1]=k;
391
downheap(1); /* Put into queue */
392
left[k]=i;
393
right[k]=j;
394
} while(heapsize>1);
395
sortptr=codeparm;
396
make_len(k);
397
make_code(nparm, lenparm, codeparm);
398
return(k); /* Return root */
399
}
400
401
/* Counts the cumulative frequency */
402
403
void count_t_freq()
404
{
405
int i, k, n, count;
406
407
for(i=0; i<NT; i++)
408
t_freq[i]=0;
409
n=NC;
410
while(n>0&&c_len[n-1]==0)
411
n--;
412
i=0;
413
while(i<n)
414
{
415
k=c_len[i++];
416
if(k==0)
417
{
418
count=1;
419
while(i<n&&c_len[i]==0)
420
{
421
i++;
422
count++;
423
}
424
if(count<=2)
425
t_freq[0]+=count;
426
else if(count<=18)
427
t_freq[1]++;
428
else if(count==19)
429
{
430
t_freq[0]++;
431
t_freq[1]++;
432
}
433
else
434
t_freq[2]++;
435
}
436
else
437
t_freq[k+2]++;
438
}
439
}
440
441
/* Writes the encoded length */
442
443
void write_pt_len(int n, int nbit, int i_special)
444
{
445
int i, k;
446
447
while(n>0&&pt_len[n-1]==0)
448
n--;
449
putbits(nbit, n);
450
i=0;
451
while(i<n)
452
{
453
k=(int)pt_len[i++];
454
if(k<=6)
455
{
456
putbits(3, k);
457
}
458
else
459
putbits(k-3, 0xFFFE);
460
if(i==i_special)
461
{
462
while(i<6&&pt_len[i]==0)
463
i++;
464
putbits(2, i-3);
465
}
466
}
467
}
468
469
/* Writes character length */
470
471
void write_c_len()
472
{
473
int i, k, n, count;
474
475
n=NC;
476
while(n>0&&c_len[n-1]==0)
477
n--;
478
putbits(CBIT, n);
479
i=0;
480
while(i<n)
481
{
482
k=(int)c_len[i++];
483
if(k==0)
484
{
485
count=1;
486
while(i<n&&c_len[i]==0)
487
{
488
i++;
489
count++;
490
}
491
if(count<=2)
492
{
493
for(k=0; k<count; k++)
494
putbits(pt_len[0], pt_code[0]);
495
}
496
else if(count<=18)
497
{
498
putbits(pt_len[1], pt_code[1]);
499
putbits(4, count-3);
500
}
501
else if(count==19)
502
{
503
putbits(pt_len[0], pt_code[0]);
504
putbits(pt_len[1], pt_code[1]);
505
putbits(4, 15);
506
}
507
else
508
{
509
putbits(pt_len[2], pt_code[2]);
510
putbits(CBIT, count-20);
511
}
512
}
513
else
514
putbits(pt_len[k+2], pt_code[k+2]);
515
}
516
}
517
518
/* Encodes a block and writes it to the output file */
519
520
void send_block()
521
{
522
unsigned int i, k, flags=0, root, pos, size;
523
unsigned int c;
524
525
if(!unpackable)
526
{
527
root=make_tree(NC, c_freq, c_len, c_code);
528
size=c_freq[root];
529
putbits(16, size);
530
if(root>=NC)
531
{
532
count_t_freq();
533
root=make_tree(NT, t_freq, pt_len, (unsigned short FAR *)pt_code);
534
if(root>=NT)
535
write_pt_len(NT, TBIT, 3);
536
else
537
{
538
putbits(TBIT, 0);
539
putbits(TBIT, root);
540
}
541
write_c_len();
542
}
543
else
544
{
545
putbits(TBIT, 0);
546
putbits(TBIT, 0);
547
putbits(CBIT, 0);
548
putbits(CBIT, root);
549
}
550
root=make_tree(NP, p_freq, pt_len, (unsigned short FAR *)pt_code);
551
if(root>=NP)
552
write_pt_len(NP, PBIT, -1);
553
else
554
{
555
putbits(PBIT, 0);
556
putbits(PBIT, root);
557
}
558
pos=0;
559
for(i=0; i<size; i++)
560
{
561
if(unpackable)
562
return;
563
if(i%CHAR_BIT==0)
564
flags=buf[pos++];
565
else
566
flags<<=1;
567
if(flags&(1U<<(CHAR_BIT-1)))
568
{
569
c=(unsigned int)buf[pos++]+(1<<CHAR_BIT);
570
encode_c(c);
571
k=buf[pos++];
572
k|=(unsigned int)buf[pos++]<<CHAR_BIT;
573
encode_p(k);
574
}
575
else
576
{
577
c=buf[pos++];
578
encode_c(c);
579
}
580
}
581
for(i=0; i<NC; i++)
582
c_freq[i]=0;
583
for(i=0; i<NP; i++)
584
p_freq[i]=0;
585
}
586
}
587
588
/* Handy macro for retrieval of two bytes (don't care about the portability) */
589
590
#ifdef ALIGN_POINTERS
591
#define word_ptr(c) ( (((unsigned char *) (c))[0]<<8)+ ((unsigned char *) (c))[1] )
592
#define _diff(c1,c2) ( (c1)[0]!=(c2)[0] || (c1)[1]!=(c2)[1] )
593
#elif !defined(TILED)
594
#define word_ptr(c) (*(unsigned short *)(c))
595
#endif
596
597
/* Tree update routine. Possibly the most time-consuming one. */
598
599
static int upd_tree(int n_c)
600
{
601
#ifdef ASM8086
602
asm{
603
push bp
604
push si
605
push di
606
mov si, n_c
607
mov bp, 1
608
mov es, word ptr dtree+2
609
mov bx, si
610
mov bx, es:[bx+si]
611
or bx, bx
612
jl done_dup
613
}
614
ok:
615
asm{
616
mov di, tree
617
add si, di
618
add di, bx
619
mov ax, [si]
620
cld
621
mov dx, numchars
622
dec dx
623
jge ut_loop
624
}
625
done_dup:
626
asm{
627
jmp done
628
}
629
ut_fetch:
630
asm{
631
mov ax, [bp+si-1]
632
}
633
select_pos:
634
asm{
635
mov di, tree
636
add di, bp
637
}
638
ut_loopbody:
639
asm{
640
dec dx
641
jl ut_brk
642
shl bx, 1
643
mov bx, es:[bx]
644
or bx, bx
645
jl ut_brk
646
cmp ax, [bx+di-1]
647
jz ut_rcount
648
dec dx
649
shl bx, 1
650
mov bx, es:[bx]
651
or bx, bx
652
jl ut_brk
653
cmp ax, [bx+di-1]
654
je ut_rcount
655
dec dx
656
shl bx, 1
657
mov bx, es:[bx]
658
or bx, bx
659
jl ut_brk
660
cmp ax, [bx+di-1]
661
je ut_rcount
662
dec dx
663
shl bx, 1
664
mov bx, es:[bx]
665
or bx, bx
666
jl ut_brk
667
cmp ax, [bx+di-1]
668
je ut_rcount
669
dec dx
670
shl bx, 1
671
mov bx, es:[bx]
672
or bx, bx
673
jl ut_brk
674
cmp ax, [bx+di-1]
675
je ut_rcount
676
dec dx
677
shl bx, 1
678
mov bx, es:[bx]
679
or bx, bx
680
jl ut_brk
681
cmp ax, [bx+di-1]
682
je ut_rcount
683
jmp short ut_loopbody
684
}
685
ut_brk:
686
asm{
687
jmp short upd_finish
688
}
689
ut_rcount:
690
asm{
691
sub di, bp
692
add di, bx
693
}
694
ut_loop:
695
asm{
696
mov cx, [si]
697
cmp cx, [di]
698
jnz select_pos
699
mov ax, ds
700
mov es, ax
701
mov ax, di
702
add di, 2
703
add si, 2
704
mov cx, 128
705
repe cmpsw
706
mov cl, [di-2]
707
sub cl, [si-2]
708
xchg ax, di
709
sub ax, di
710
sub si, ax
711
sub cl, 1
712
adc ax, -2
713
mov es, word ptr dtree+2
714
cmp ax, bp
715
jg verify_pos
716
jmp ut_fetch
717
}
718
verify_pos:
719
asm{
720
mov cx, si
721
sub cx, di
722
cmp cx, dicsiz_cur
723
jg upd_finish
724
dec cx
725
mov dicpos, cx
726
mov bp, ax
727
cmp bp, 256
728
jge upd_finish
729
jmp ut_fetch
730
}
731
upd_finish:
732
asm{
733
cmp bp, 256
734
jle done
735
mov bp, 256
736
}
737
done:
738
asm{
739
mov ax, bp
740
mov tc_passes, ax
741
pop di
742
pop si
743
pop bp
744
}
745
return(tc_passes);
746
#else
747
short FAR *dptr;
748
short r_bx, r_dx;
749
unsigned short r_ax;
750
short r_bp=1;
751
unsigned char *tptr;
752
unsigned char *tdptr;
753
unsigned char *prev_tptr, *prev_tdptr;
754
int c;
755
char diff;
756
int remainder;
757
758
dptr=dtree;
759
if((r_bx=dptr[n_c])>=0)
760
{
761
tptr=tree+n_c;
762
tdptr=tree+r_bx;
763
r_ax=word_ptr(tptr);
764
r_dx=numchars;
765
if(--r_dx>=0)
766
goto ut_loop;
767
ut_fetch:
768
r_ax=word_ptr(tptr+r_bp-1);
769
select_pos:
770
tdptr=tree+r_bp;
771
do
772
{
773
if(--r_dx<0)
774
goto upd_finish;
775
r_bx=dptr[r_bx];
776
if(r_bx<0)
777
goto upd_finish;
778
} while(r_ax!=word_ptr(tdptr+r_bx-1));
779
tdptr+=r_bx-r_bp;
780
ut_loop:
781
#ifdef ALIGN_POINTERS
782
if (_diff(tptr,tdptr))
783
#else
784
if(word_ptr(tptr)!=word_ptr(tdptr))
785
#endif
786
goto select_pos;
787
prev_tptr=tptr;
788
prev_tdptr=tdptr;
789
tptr+=2;
790
tdptr+=2;
791
for(c=128; c>0; c--)
792
{
793
#ifdef ALIGN_POINTERS
794
if (_diff(tptr,tdptr))
795
#else
796
if(word_ptr(tptr)!=word_ptr(tdptr))
797
#endif
798
break;
799
tptr+=2;
800
tdptr+=2;
801
}
802
diff=*(tdptr)-*(tptr);
803
remainder=tdptr-prev_tdptr;
804
if(diff==0)
805
remainder+=1;
806
tptr=prev_tptr;
807
tdptr=prev_tdptr;
808
if(remainder<=r_bp)
809
goto ut_fetch;
810
if(tptr-tdptr<=dicsiz_cur)
811
{
812
dicpos=tptr-tdptr-1;
813
r_bp=remainder;
814
if(r_bp<256)
815
goto ut_fetch;
816
}
817
upd_finish:
818
if(r_bp>256)
819
r_bp=256;
820
}
821
return(tc_passes=r_bp);
822
#endif
823
}
824
825
/* Optimized output routine */
826
827
static void output(int c, unsigned short p)
828
{
829
unsigned char FAR *bptr;
830
unsigned char cy;
831
unsigned short r_dx;
832
unsigned short r_bx;
833
834
bptr=buf;
835
r_dx=cpos;
836
cy=output_mask&1;
837
output_mask=(cy?0x80:0)|((output_mask&0xFF)>>1);
838
if(cy)
839
{
840
if(r_dx>=bufsiz)
841
{
842
send_block();
843
if(unpackable)
844
{
845
cpos=bptr-buf;
846
return;
847
}
848
r_dx=0;
849
}
850
output_pos=r_dx;
851
buf[r_dx]=0;
852
r_dx++;
853
}
854
bptr+=r_dx;
855
*bptr++=c;
856
c_freq[c]++;
857
if(c>=256)
858
{
859
buf[output_pos]|=output_mask;
860
*bptr++=p&0xFF;
861
*bptr++=(p>>8);
862
for(r_bx=0; p!=0; p>>=1)
863
r_bx++;
864
p_freq[r_bx]++;
865
}
866
cpos=bptr-buf;
867
}
868
869
/* Unstubbed optimized output routine */
870
871
static void output_opt(unsigned char c)
872
{
873
unsigned char FAR *bptr, FAR *cptr;
874
unsigned short r_dx;
875
unsigned char cy;
876
877
cptr=bptr=buf;
878
r_dx=cpos;
879
cy=output_mask&1;
880
output_mask=(cy?0x80:0)|((output_mask&0xFF)>>1);
881
if(cy)
882
{
883
if(r_dx>=bufsiz)
884
{
885
send_block();
886
r_dx=0;
887
if(unpackable)
888
{
889
cpos=r_dx;
890
return;
891
}
892
}
893
output_pos=r_dx;
894
cptr[r_dx]=0;
895
r_dx++;
896
}
897
bptr+=r_dx;
898
*bptr++=c;
899
c_freq[c]++;
900
cpos=bptr-cptr;
901
}
902
903
/* Initializes memory for encoding */
904
905
void allocate_memory()
906
{
907
int i;
908
909
if((c_freq=calloc(NC*2-1, sizeof(*c_freq)))==NULL)
910
error(M_OUT_OF_NEAR_MEMORY);
911
if((c_code=farcalloc(NC, sizeof(*c_code)))==NULL)
912
error(M_OUT_OF_MEMORY);
913
if((heap=farcalloc(NC+1, sizeof(*heap)))==NULL)
914
error(M_OUT_OF_MEMORY);
915
for(i=0; i<NP; i++)
916
p_freq[i]=0;
917
depth=0;
918
bufsiz=current_bufsiz;
919
if(bufsiz>=MAX_BUFSIZ-BUFSIZ_INCREMENT)
920
bufsiz=MAX_BUFSIZ-1;
921
#ifdef FINETUNE_BUFSIZ
922
i=1;
923
#endif
924
/* Adjust the buffer size if there's not enough memory for it */
925
while((buf=farmalloc(bufsiz))==NULL)
926
{
927
#ifndef FINETUNE_BUFSIZ
928
bufsiz=bufsiz/10U*9U;
929
#else
930
if(i<2048)
931
bufsiz-=i++;
932
else
933
bufsiz=bufsiz/16U*15U;
934
#endif
935
if(bufsiz<MIN_BUFSIZ)
936
error(M_OUT_OF_MEMORY);
937
}
938
if(debug_enabled&&strchr(debug_opt, 'v')!=NULL)
939
msg_cprintf(0, M_BUFSIZ, bufsiz);
940
init_putbits();
941
output_mask=1;
942
output_pos=0;
943
cpos=0;
944
buf[output_pos]='\0';
945
bufsiz-=30;
946
}
947
948
/* Shutdown the encoding */
949
950
void NEAR huf_encode_end()
951
{
952
if(!unpackable)
953
send_block();
954
shutdown_putbits();
955
free(c_freq);
956
farfree(c_code);
957
farfree(heap);
958
farfree(buf);
959
bufsiz=0;
960
cpos=0;
961
}
962
963
/* Basic encoding routine */
964
965
static void NEAR huf_encode()
966
{
967
int hash_bits;
968
unsigned short fp_max;
969
int nchars;
970
int i, j, m=0;
971
short k, l;
972
unsigned short t; /* Exchange variable */
973
int tree_el;
974
unsigned int n_passes;
975
unsigned int f_dicpos;
976
unsigned int fetch;
977
unsigned int max_fetch; /* For comparison */
978
short FAR *fptr;
979
short FAR *dtptr;
980
unsigned char *tptr;
981
unsigned short r_cx, r_dx, r_ax;
982
int pm;
983
984
hash_bits=(dicbit+2)/3;
985
fpcount=1U<<dicbit;
986
fp_max=fpcount-1;
987
if(tree==NULL)
988
{
989
if((tree=calloc(treesize+2, sizeof(*tree)))==NULL)
990
error(M_OUT_OF_NEAR_MEMORY);
991
#ifdef ASM8086
992
ftree=farcalloc_based((unsigned long)treesize+16L, sizeof(*ftree));
993
dtree=(FP_OFF(ftree)==0)?ftree:MK_FP(FP_SEG(ftree)+((FP_OFF(ftree)+15)>>4), 0);
994
#else
995
ftree=dtree=farcalloc((unsigned long)treesize+16L, sizeof(*ftree));
996
#endif
997
fpbuf=farcalloc((unsigned long)fpcount+4L, 2L);
998
if(ftree==NULL||fpbuf==NULL)
999
error(M_OUT_OF_MEMORY);
1000
}
1001
if(dic_alloc<1024)
1002
dic_alloc=1024;
1003
allocate_memory();
1004
nchars=(UCHAR_MAX+THRESHOLD)*2;
1005
display_indicator(0L);
1006
encoded_bytes=0L;
1007
tc_passes=0;
1008
dicpos=0;
1009
i=j=0;
1010
while(!unpackable)
1011
{
1012
tree_el=0;
1013
k=0;
1014
if(j!=0)
1015
{
1016
tree_el=dic_alloc;
1017
if((k=j-tree_el)<=0)
1018
{
1019
k=0;
1020
tree_el=j;
1021
}
1022
else
1023
memmove(tree, tree+k, tree_el);
1024
}
1025
max_fetch=fetch=(unsigned int)(treesize-tree_el);
1026
if(multivolume_option)
1027
fetch=check_multivolume(fetch);
1028
if(max_fetch!=fetch)
1029
nchars=4;
1030
if((fetch=fetch_uncomp(tree+tree_el, fetch))==0)
1031
{
1032
if(tree_el==0||k==0)
1033
break;
1034
memmove(tree+k, tree, tree_el);
1035
dicsiz_cur=min(tree_el-i-1, dicsiz_cur);
1036
break;
1037
}
1038
j=fetch+tree_el;
1039
encoded_bytes+=(unsigned long)fetch;
1040
display_indicator(encoded_bytes);
1041
m=0;
1042
if(k<=0)
1043
fill_fpbuf();
1044
else
1045
{
1046
fptr=fpbuf;
1047
for(l=fpcount>>2; l>0; l--)
1048
{
1049
*fptr=max(*fptr-k, -1);
1050
fptr++;
1051
*fptr=max(*fptr-k, -1);
1052
fptr++;
1053
*fptr=max(*fptr-k, -1);
1054
fptr++;
1055
*fptr=max(*fptr-k, -1);
1056
fptr++;
1057
}
1058
dtptr=dtree;
1059
for(l=tree_el>>3; l>0; l--)
1060
{
1061
*dtptr=max(dtptr[k]-k, -1);
1062
dtptr++;
1063
*dtptr=max(dtptr[k]-k, -1);
1064
dtptr++;
1065
*dtptr=max(dtptr[k]-k, -1);
1066
dtptr++;
1067
*dtptr=max(dtptr[k]-k, -1);
1068
dtptr++;
1069
*dtptr=max(dtptr[k]-k, -1);
1070
dtptr++;
1071
*dtptr=max(dtptr[k]-k, -1);
1072
dtptr++;
1073
*dtptr=max(dtptr[k]-k, -1);
1074
dtptr++;
1075
*dtptr=max(dtptr[k]-k, -1);
1076
dtptr++;
1077
}
1078
/* Store the remainder */
1079
for(l=tree_el%8; l>0; l--)
1080
{
1081
*dtptr=max(dtptr[k]-k, -1);
1082
dtptr++;
1083
}
1084
m+=tree_el;
1085
if(m>=2)
1086
m-=2;
1087
}
1088
tptr=&tree[m];
1089
r_dx=(unsigned short)*(tptr++);
1090
r_cx=(fp_max&0xFF00)|(hash_bits&0xFF);
1091
r_dx<<=(hash_bits&0xFF);
1092
r_dx^=(unsigned short)*(tptr++);
1093
r_dx&=(r_cx|0xFF);
1094
for(l=j-2; m<l; m++)
1095
{
1096
r_dx<<=(r_cx&0xFF);
1097
r_dx^=*(tptr++);
1098
r_dx&=(r_cx|0xFF);
1099
t=fpbuf[r_dx];
1100
fpbuf[r_dx]=m;
1101
dtree[m]=t;
1102
}
1103
dtree[m]=-1;
1104
dtree[m+1]=-1;
1105
m=tree_el-i;
1106
i+=fetch;
1107
while(i>nchars)
1108
{
1109
i--;
1110
pm=m;
1111
m++;
1112
n_passes=(unsigned int)tc_passes;
1113
f_dicpos=(int)dicpos;
1114
if((r_ax=upd_tree(m))>i)
1115
r_ax=tc_passes=i;
1116
if(n_passes<THRESHOLD||(n_passes==THRESHOLD&&f_dicpos>16384)||--r_ax>n_passes||(r_ax==n_passes&&dicpos>>1<f_dicpos))
1117
{
1118
output_opt(tree[pm]);
1119
}
1120
else
1121
{
1122
i-=n_passes-1;
1123
m+=n_passes-1;
1124
r_ax=n_passes+UCHAR_MAX-2;
1125
output(r_ax, f_dicpos);
1126
upd_tree(m);
1127
if(tc_passes>i)
1128
tc_passes=i;
1129
}
1130
}
1131
}
1132
while(i>0)
1133
{
1134
i--;
1135
pm=m;
1136
m++;
1137
n_passes=tc_passes;
1138
f_dicpos=dicpos;
1139
if((r_ax=upd_tree(m))>i)
1140
r_ax=tc_passes=i;
1141
if(n_passes<THRESHOLD||(n_passes==THRESHOLD&&f_dicpos>16384)||--r_ax>n_passes||(r_ax==n_passes&&dicpos>>1<f_dicpos))
1142
{
1143
output_opt(tree[pm]);
1144
}
1145
else
1146
{
1147
i-=n_passes-1;
1148
m+=n_passes-1;
1149
r_ax=n_passes+UCHAR_MAX-2;
1150
output(r_ax, f_dicpos);
1151
if((r_ax=upd_tree(m))>i)
1152
tc_passes=i;
1153
}
1154
}
1155
huf_encode_end();
1156
#ifdef ASM8086
1157
farfree_based(ftree);
1158
#else
1159
farfree(ftree);
1160
#endif
1161
farfree(fpbuf);
1162
free(tree);
1163
tree=NULL;
1164
}
1165
1166
/* Encoding stub for -m3 */
1167
1168
static void NEAR huf_encode_m3()
1169
{
1170
int hash_bits;
1171
unsigned short fp_max;
1172
int i, j, m;
1173
unsigned short t; /* Exchange variable */
1174
short k, l;
1175
int tree_el;
1176
unsigned int fetch;
1177
unsigned char *tptr;
1178
unsigned short r_cx, r_dx;
1179
short r_ax;
1180
1181
hash_bits=(dicbit+2)/3;
1182
fpcount=1U<<dicbit;
1183
fp_max=fpcount-1;
1184
if(tree==NULL)
1185
{
1186
if((tree=calloc(treesize+2, sizeof(*tree)))==NULL)
1187
error(M_OUT_OF_NEAR_MEMORY);
1188
#ifdef ASM8086
1189
ftree=farcalloc_based((unsigned long)treesize+16L, sizeof(*ftree));
1190
dtree=(FP_OFF(ftree)==0)?ftree:MK_FP(FP_SEG(ftree)+((FP_OFF(ftree)+15)>>4), 0);
1191
#else
1192
ftree=dtree=farcalloc((unsigned long)treesize+16L, sizeof(*ftree));
1193
#endif
1194
fpbuf=farcalloc((unsigned long)fpcount+4L, 2L);
1195
if(ftree==NULL||fpbuf==NULL)
1196
error(M_OUT_OF_MEMORY);
1197
}
1198
allocate_memory();
1199
display_indicator(encoded_bytes=0L);
1200
j=0;
1201
while(!unpackable)
1202
{
1203
tree_el=0;
1204
if(dic_alloc!=0&&j!=0)
1205
{
1206
tree_el=dic_alloc;
1207
if((k=j-tree_el)<=0)
1208
{
1209
k=0;
1210
tree_el=j;
1211
}
1212
else
1213
memmove(tree, tree+k, tree_el);
1214
}
1215
fetch=(unsigned int)(treesize-tree_el);
1216
if(multivolume_option)
1217
fetch=check_multivolume(fetch);
1218
if((fetch=fetch_uncomp(tree+tree_el, fetch))==0)
1219
break;
1220
else
1221
{
1222
j=fetch+tree_el;
1223
encoded_bytes+=(unsigned long)fetch;
1224
display_indicator(encoded_bytes);
1225
fill_fpbuf();
1226
l=fetch;
1227
tptr=tree;
1228
r_dx=(unsigned short)*(tptr++);
1229
r_cx=(fp_max&0xFF00)|(hash_bits&0xFF);
1230
r_dx<<=(hash_bits&0xFF);
1231
r_dx^=(unsigned short)*(tptr++);
1232
r_dx&=(r_cx|0xFF);
1233
for(m=0; m<j; m++)
1234
{
1235
r_dx<<=(r_cx&0xFF);
1236
r_dx^=*(tptr++);
1237
r_dx&=(r_cx|0xFF);
1238
t=fpbuf[r_dx];
1239
fpbuf[r_dx]=m;
1240
dtree[m]=t;
1241
}
1242
i=l;
1243
m=tree_el;
1244
while(i>0)
1245
{
1246
r_ax=upd_tree(m);
1247
if((r_ax=upd_tree(m))>i)
1248
r_ax=tc_passes=i;
1249
if(r_ax<THRESHOLD)
1250
{
1251
r_ax=(unsigned short)tree[m];
1252
output(r_ax, 0);
1253
m++;
1254
i--;
1255
}
1256
else
1257
{
1258
r_ax+=UCHAR_MAX-2;
1259
output(r_ax, dicpos);
1260
m+=tc_passes;
1261
i-=tc_passes;
1262
}
1263
}
1264
}
1265
}
1266
huf_encode_end();
1267
#ifdef ASM8086
1268
farfree_based(ftree);
1269
#else
1270
farfree(ftree);
1271
#endif
1272
farfree(fpbuf);
1273
free(tree);
1274
tree=NULL;
1275
}
1276
1277
/* Encodes a single file. */
1278
1279
void encode(int method)
1280
{
1281
char *dsw; /* Debug switch (-hd) pointer */
1282
char a;
1283
1284
numchars=UCHAR_MAX+5;
1285
dicbit=14;
1286
dic_alloc=DICSIZ;
1287
treesize=31744;
1288
dicsiz_cur=DICSIZ-2;
1289
adjust_dicbit();
1290
/* Method 0 (store) is already filtered away at this point */
1291
switch(method)
1292
{
1293
case 1:
1294
numchars=UCHAR_MAX+5;
1295
break;
1296
case 2:
1297
treesize=30720;
1298
numchars=72;
1299
dic_alloc=20480;
1300
break;
1301
case 3:
1302
treesize=30720;
1303
numchars=32;
1304
dic_alloc=8192;
1305
break;
1306
default:
1307
error(M_UNKNOWN_METHOD);
1308
}
1309
switch(max_compression)
1310
{
1311
case 1:
1312
numchars=3000;
1313
dic_alloc=DICSIZ+512;
1314
break;
1315
case 2:
1316
numchars=512;
1317
dic_alloc=DICSIZ+512;
1318
break;
1319
case 3:
1320
numchars=1024;
1321
dicbit=12;
1322
treesize=20480;
1323
dicsiz_cur=dic_alloc=16384;
1324
break;
1325
case 4:
1326
numchars=1024;
1327
dicbit=12;
1328
treesize=12288;
1329
dicsiz_cur=dic_alloc=8192;
1330
}
1331
if(debug_enabled)
1332
{
1333
dsw=debug_opt;
1334
while(*dsw!='\0')
1335
{
1336
a=*(dsw++);
1337
switch(a)
1338
{
1339
case 'd': /* Dictionary size */
1340
dicsiz_cur=(unsigned int)strtol(dsw, &dsw, 10);
1341
break;
1342
case 'g': /* G-size */
1343
dic_alloc=(int)strtol(dsw, &dsw, 10);
1344
break;
1345
case 'h':
1346
dicbit=(int)strtol(dsw, &dsw, 10);
1347
break;
1348
case 'm':
1349
numchars=(int)strtol(dsw, &dsw, 10);
1350
break;
1351
case 'w':
1352
treesize=(int)strtol(dsw, &dsw, 10);
1353
break;
1354
}
1355
}
1356
if(strchr(debug_opt, 'v')!=NULL)
1357
msg_cprintf(0, M_PRECOMP_STAT, numchars, dicbit, dicsiz_cur, dic_alloc, treesize);
1358
}
1359
if(dicsiz_cur>DICSIZ_MAX)
1360
error(M_LARGE_DICTIONARY);
1361
if(dic_alloc>treesize)
1362
error(M_LARGE_GSIZE);
1363
if(method==3)
1364
huf_encode_m3();
1365
else
1366
huf_encode();
1367
}
1368
1369
/* Fast search stub for method 4 */
1370
1371
static void enc4_pass1(int n_c)
1372
{
1373
#ifdef ASM8086
1374
asm{
1375
mov dx, n_c
1376
mov bx, 1
1377
mov cx, 0
1378
cmp dx, bx
1379
jl cease_search
1380
}
1381
binsearch:
1382
asm{
1383
sub dx, bx
1384
inc cx
1385
shl bx, 1
1386
cmp dx, bx
1387
jl cease_search
1388
sub dx, bx
1389
inc cx
1390
shl bx, 1
1391
cmp dx, bx
1392
jl cease_search
1393
sub dx, bx
1394
inc cx
1395
shl bx, 1
1396
cmp dx, bx
1397
jl cease_search
1398
sub dx, bx
1399
inc cx
1400
shl bx, 1
1401
cmp dx, bx
1402
jl cease_search
1403
sub dx, bx
1404
inc cx
1405
shl bx, 1
1406
cmp dx, bx
1407
jl cease_search
1408
jmp binsearch
1409
}
1410
cease_search:
1411
asm{
1412
or cx, cx
1413
jz chk_ctr_bounds
1414
push dx
1415
push cx
1416
mov ax, 65535
1417
push ax
1418
push cx
1419
call far ptr putbits
1420
add sp, 4
1421
pop cx
1422
pop dx
1423
}
1424
chk_ctr_bounds:
1425
asm{
1426
cmp cx, 7
1427
jge p1exit
1428
inc cx
1429
}
1430
p1exit:
1431
asm{
1432
push dx
1433
push cx
1434
call far ptr putbits
1435
add sp, 4
1436
}
1437
#else
1438
short r_bx=1;
1439
int r_cx=0;
1440
1441
while(n_c>=r_bx)
1442
{
1443
n_c-=r_bx;
1444
r_cx++;
1445
r_bx<<=1;
1446
}
1447
if(r_cx!=0)
1448
putbits(r_cx, -1);
1449
if(r_cx<7)
1450
r_cx++;
1451
putbits(r_cx, n_c);
1452
#endif
1453
}
1454
1455
/* Dictionary position lookup */
1456
1457
static void enc4_pass2(int n_c)
1458
{
1459
#ifdef ASM8086
1460
asm{
1461
mov dx, n_c
1462
mov bx, 512
1463
mov cx, 9
1464
cmp dx, bx
1465
jl p2_cease_search
1466
}
1467
p2_bsearch:
1468
asm{
1469
sub dx, bx
1470
inc cx
1471
shl bx, 1
1472
cmp dx, bx
1473
jl p2_cease_search
1474
sub dx, bx
1475
inc cx
1476
shl bx, 1
1477
cmp dx, bx
1478
jl p2_cease_search
1479
sub dx, bx
1480
inc cx
1481
shl bx, 1
1482
cmp dx, bx
1483
jl p2_cease_search
1484
sub dx, bx
1485
inc cx
1486
shl bx, 1
1487
cmp dx, bx
1488
jl p2_cease_search
1489
sub dx, bx
1490
inc cx
1491
shl bx, 1
1492
cmp dx, bx
1493
jge p2_bsearch
1494
}
1495
p2_cease_search:
1496
asm{
1497
mov ch, cl
1498
sub cl, 9
1499
jz p2_chk_ctr
1500
push cx
1501
push dx
1502
mov ax, 65535
1503
push ax
1504
push cx
1505
call far ptr putbits
1506
add sp, 4
1507
pop dx
1508
pop cx
1509
}
1510
p2_chk_ctr:
1511
asm{
1512
cmp ch, 13
1513
jge p2exit
1514
inc ch
1515
}
1516
p2exit:
1517
asm{
1518
mov cl, ch
1519
push dx
1520
push cx
1521
call far ptr putbits
1522
add sp, 4
1523
}
1524
#else
1525
unsigned short r_bx=1<<9;
1526
int r_cx=9;
1527
1528
while(n_c>=r_bx)
1529
{
1530
n_c-=r_bx;
1531
r_cx++;
1532
r_bx<<=1;
1533
}
1534
if(r_cx!=9)
1535
putbits(r_cx-9, -1);
1536
if(r_cx<13)
1537
r_cx++;
1538
putbits(r_cx, n_c);
1539
#endif
1540
}
1541
1542
/* Encodes a single file, using method 4 */
1543
1544
void encode_f()
1545
{
1546
int fetch;
1547
int hash_bits;
1548
unsigned short fp_max;
1549
unsigned char *tptr;
1550
int i, m;
1551
unsigned short r_cx, r_dx, r_ax;
1552
unsigned short t;
1553
1554
dicbit=14;
1555
numchars=32;
1556
dicsiz_cur=15800;
1557
treesize=30720;
1558
adjust_dicbit();
1559
hash_bits=(dicbit+2)/3;
1560
fpcount=1U<<dicbit;
1561
fp_max=fpcount-1;
1562
if(tree==NULL)
1563
{
1564
if((tree=calloc(treesize+2, sizeof(*tree)))==NULL)
1565
error(M_OUT_OF_NEAR_MEMORY);
1566
#ifdef ASM8086
1567
ftree=farcalloc_based((unsigned long)treesize+16L, sizeof(*ftree));
1568
dtree=(FP_OFF(ftree)==0)?ftree:MK_FP(FP_SEG(ftree)+((FP_OFF(ftree)+15)>>4), 0);
1569
#else
1570
ftree=dtree=farcalloc((unsigned long)treesize+16L, sizeof(*ftree));
1571
#endif
1572
fpbuf=farcalloc((unsigned long)fpcount+4L, 2L);
1573
if(ftree==NULL||fpbuf==NULL)
1574
error(M_OUT_OF_MEMORY);
1575
}
1576
init_putbits();
1577
cpos=0;
1578
display_indicator(encoded_bytes=0L);
1579
while(!unpackable)
1580
{
1581
fetch=treesize;
1582
if(multivolume_option)
1583
fetch=check_multivolume(fetch);
1584
if((fetch=fetch_uncomp(tree, fetch))==0)
1585
break;
1586
encoded_bytes+=(unsigned long)fetch;
1587
display_indicator(encoded_bytes);
1588
fill_fpbuf();
1589
m=0;
1590
tptr=tree;
1591
r_dx=(unsigned short)*(tptr++);
1592
r_cx=(fp_max&0xFF00)|(hash_bits&0xFF);
1593
r_dx<<=(hash_bits&0xFF);
1594
r_dx^=(unsigned short)*(tptr++);
1595
r_dx&=(r_cx|0xFF);
1596
for(m=0; m<fetch; m++)
1597
{
1598
r_dx<<=(r_cx&0xFF);
1599
r_dx^=(unsigned char)*(tptr++);
1600
r_dx&=(r_cx|0xFF);
1601
t=fpbuf[r_dx];
1602
fpbuf[r_dx]=m;
1603
dtree[m]=t;
1604
}
1605
m=0;
1606
i=fetch;
1607
while(i>0)
1608
{
1609
if((r_ax=upd_tree(m))>i)
1610
r_ax=tc_passes=i;
1611
if(r_ax<THRESHOLD)
1612
{
1613
putbits(9, (unsigned char)tree[m]);
1614
i--;
1615
m++;
1616
}
1617
else
1618
{
1619
i-=tc_passes;
1620
m+=tc_passes;
1621
r_ax=tc_passes-2;
1622
enc4_pass1(r_ax);
1623
enc4_pass2(dicpos);
1624
}
1625
}
1626
}
1627
shutdown_putbits();
1628
farfree(fpbuf);
1629
#ifdef ASM8086
1630
farfree_based(ftree);
1631
#else
1632
farfree(ftree);
1633
#endif
1634
free(tree);
1635
tree=NULL;
1636
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1