unhuf.S@ 16444

Last change on this file since 16444 was 1, checked in by vboxsync, 55 years ago
import
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 9.5 KB

Line
1	/*****************************************************************************
2	* NOTE: This code is no longer used in Etherboot. The obsolete
3	* Makefile target .lzrom refers to it, but it is no longer being
4	* maintained and may no longer work. Use .zrom instead (which uses
5	* the unnrv2b decompressor).
6	*****************************************************************************
7	*/
8
9	/* At entry, the processor is in 16 bit real mode and the code is being
10	* executed from an address it was not linked to. Code must be pic and
11	* 32 bit sensitive until things are fixed up.
12	*/
13
14
15	/* LZHuf (LZSS) Decompressing boot loader for ROM images
16	*
17	* this code is based on the work of Haruyasu Yoshizaki and Haruhiko Okumura
18	* who implemented the original compressor and decompressor in C code
19	*
20	* Converted to 32bit assembly 16 July 2002 Eric Biederman <[email protected]>
21	* Made PIC 10 Aug 2002 Eric Biederman <[email protected]>
22	*
23	* Copyright 1997 by M. Gutschke <[email protected]>
24	*
25	* Compression pays off, as soon as the uncompressed image is bigger than
26	* about 1.5kB. This assumes an average compressibility of about 60%.
27	*/
28
29
30	/* Do not change these values unless you really know what you are doing
31	* the pre-computed lookup tables rely on the buffer size being 4kB or
32	* smaller. The buffer size must be a power of two. The lookahead size has
33	* to fit into 6 bits. If you change any of these numbers, you will also
34	* have to adjust the compressor accordingly.
35	*/
36	#define BUFSZ 4096
37	#define LOOKAHEAD 60
38	#define THRESHOLD 2
39	#define NCHAR (256+LOOKAHEAD-THRESHOLD)
40	#define TABLESZ (NCHAR+NCHAR-1)
41	#define ROOT (TABLESZ-1)
42
43	.text
44	.arch i386
45	.globl _start
46	_start:
47	cli
48
49	/* Save the initial register values */
50	pushal
51
52	/*
53	* See where I am running, and compute %ebp
54	*/
55	call 1f
56	1: pop %ebp
57	subl $1b, %ebp
58
59	/*
60	* INIT -- initializes all data structures
61	* ====
62	*/
63
64	init:
65	cld
66	leal dcodrle(%ebp), %esi /* uncompress run length encoded */
67	leal dcode(%ebp), %edi /* lookup table for codes */
68	movb $6, %dl
69	movb $0x20, %dh
70	xorb %bh,%bh
71	init0:
72	lodsb
73	movb %al,%bl
74	init1:
75	xorl %ecx, %ecx
76	movb %dh,%cl
77	movb %bh,%al
78	rep
79	stosb
80	incb %bh
81	decb %bl
82	jnz init1
83	shrb %dh
84	decb %dl
85	jnz init0
86	movb $1, %bl /* uncompress run length encoded */
87	movb $6, %bh /* lookup table for code lengths */
88	init2:
89	lodsb
90	xorl %ecx, %ecx
91	movb %al,%cl
92	movb %bl,%al
93	rep
94	stosb
95	incb %bl
96	decb %bh
97	jnz init2
98
99	movl $NCHAR, %ecx /* set all frequencies of leaf nodes */
100	movw $1, %ax /* to one */
101	rep
102	stosw
103	leal freq(%ebp), %esi
104	movl $ROOT+1-NCHAR, %ecx
105	init3:
106	lodsw /* update frequencies of non-leaf nodes */
107	movw %ax,%bx
108	lodsw
109	addw %bx,%ax
110	stosw
111	loop init3
112	movw $0xFFFF, %ax
113	stosw /* sentinel with infinite frequency */
114	movl $NCHAR, %ecx
115	movw $TABLESZ, %ax
116	init4:
117	stosw /* update son pointers for leaf nodes */
118	incw %ax
119	loop init4
120	movl $ROOT+1-NCHAR, %ecx
121	xorw %ax,%ax
122	init5:
123	stosw /* update son ptrs for non-leaf nodes */
124	addw $2, %ax
125	loop init5
126	movl $ROOT+1-NCHAR, %ecx
127	movw $NCHAR, %ax
128	init6:
129	stosw /* update parent ptrs for non-leaf nd. */
130	stosw
131	incw %ax
132	loop init6
133	movl $NCHAR, %ecx
134	xorw %ax,%ax
135	stosw /* root node has no parent */
136	init7:
137	stosw /* update parent ptrs for leaf nodes */
138	incw %ax
139	loop init7
140	xorw %ax,%ax
141	stosb /* clear getlen */
142	stosw /* clear getbuf */
143	movb $0x20, %al /* fill text buffer with spaces */
144	leal spaces(%ebp), %edi
145	movl $BUFSZ-LOOKAHEAD, %ecx
146	rep
147
148	stosb
149	/* fall thru */
150
151	/*
152	* MAIN -- reads compressed codes and writes decompressed data
153	* ====
154	*/
155
156	leal _payload(%ebp), %esi /* get length of compressed data stream */
157	leal uncompressed(%ebp), %edi
158
159	lodsl
160	movl %eax, %ecx
161	main1:
162	pushl %ecx
163	call dcdchr /* decode one code symbol */
164	orb %ah,%ah /* test if 8bit character */
165	jnz main2
166	stosb /* store verbatim */
167	popl %ecx
168	loop main1 /* proceed with next compressed code */
169	jmp done /* until end of input is detected */
170	main2:
171	pushl %eax
172	call dcdpos /* compute position in output buffer */
173	movl %esi, %eax
174	subl %edi, %ebx
175	notl %ebx
176	movl %ebx, %esi /* si := di - dcdpos() - 1 */
177	popl %ecx
178	subl $255-THRESHOLD, %ecx /* compute length of code sequence */
179	movl %ecx, %edx
180	rep
181	movsb
182	movl %eax,%esi
183	popl %ecx
184	subl %edx, %ecx /* check end of input condition */
185	jnz main1 /* proceed with next compressed code */
186	done:
187	/* Start Etherboot */
188	popal
189	jmp uncompressed
190	/*
191	* GETBIT -- gets one bit pointed to by DS:ESI
192	* ======
193	*
194	* changes: AX,CX,DL
195	*/
196
197	getbit:
198	movb $8, %cl
199	movb getlen(%ebp), %dl /* compute number of bits required */
200	subb %dl,%cl /* to fill read buffer */
201	jae getbit1
202	movw getbuf(%ebp), %ax /* there is still enough read ahead data */
203	jmp getbit2
204	getbit1:
205	lodsb /* get next byte from input stream */
206	xorb %ah,%ah
207	shlw %cl,%ax /* shift, so that it will fit into */
208	movw getbuf(%ebp), %cx /* read ahead buffer */
209	orw %cx,%ax
210	addb $8, %dl /* update number of bits in buffer */
211	getbit2:
212	movw %ax,%cx
213	shlw %cx /* extract one bit from buffer */
214	movw %cx, getbuf(%ebp)
215	decb %dl
216	movb %dl, getlen(%ebp) /* and update number of bits */
217	shlw %ax /* return in carry flag */
218	ret
219
220
221	/*
222	* DCDPOS -- decodes position in textbuffer as pointed to by DS:SI, result in BX
223	* ======
224	*
225	* changes: AX,EBX,ECX,DX
226	*/
227
228	dcdpos:
229	movl $0x0800, %ebx
230	dcdpos1:
231	shlb %bl /* read one byte */
232	call getbit
233	jnc dcdpos2
234	incb %bl
235	dcdpos2:
236	decb %bh
237	jnz dcdpos1
238	movb %bl,%dh /* read length of code from table */
239	xorb %bh,%bh
240	xorl %ecx, %ecx
241	movb dlen(%ebx, %ebp),%cl
242	movb dcode(%ebx, %ebp),%bl /* get top six bits from table */
243	shll $6, %ebx
244	dcdpos3:
245	pushl %ecx /* read the rest from the input stream */
246	shlb %dh
247	call getbit
248	jnc dcdpos4
249	incb %dh
250	dcdpos4:
251	popl %ecx
252	loop dcdpos3
253	andb $0x3f, %dh /* combine upper and lower half of code */
254	orb %dh,%bl
255	ret
256
257	/*
258	* DCDCHR -- decodes one compressed character pointed to by DS:SI
259	* ======
260	*
261	* changes: AX,BX,CX,DX
262	*/
263
264	dcdchr:
265	movl $ROOT, %ebx /* start at root entry */
266	shll %ebx
267	movzwl son(%ebx, %ebp),%ebx
268	dcdchr1:
269	call getbit /* get a single bit */
270	jnc dcdchr2
271	incl %ebx /* travel left or right */
272	dcdchr2:
273	shll %ebx
274	movzwl son(%ebx, %ebp), %ebx
275	cmpl $TABLESZ, %ebx /* until we come to a leaf node */
276	jb dcdchr1
277	movl %ebx, %eax
278	subl $TABLESZ, %eax
279	/* fall thru */
280
281	/*
282	* UPDATE -- updates huffman tree after incrementing frequency for code in BX
283	* ======
284	*
285	* changes: BX,CX,DX
286	*/
287
288	update:
289	/* we do not check whether the frequency count has overrun.
290	* this will cause problems for large files, but be should be fine
291	* as long as the compressed size does not exceed 32kB and we
292	* cannot do more than this anyways, because we load into the
293	* upper 32kB of conventional memory
294	*/
295	pushl %esi
296	pushl %eax
297	shll %ebx
298	movzwl parent(%ebx, %ebp),%ebx
299	update1:
300	shll %ebx
301	movzwl freq(%ebx, %ebp), %edx
302	incl %edx /* increment frequency count by one */
303	movw %dx, freq(%ebx, %ebp)
304	leal 2+freq(%ebx, %ebp), %esi
305	lodsw /* check if nodes need reordering */
306	cmpw %ax, %dx
307	jbe update5
308	update2:
309	lodsw
310	cmpw %dx, %ax
311	jb update2
312	movzwl -4(%esi), %ecx
313	movw %cx, freq(%ebx, %ebp) /* swap frequency of entries */
314	movw %dx, -4(%esi)
315
316	movl %esi, %eax /* compute index of new entry */
317	subl $freq+4, %eax
318	subl %ebp, %eax
319
320	movl %eax, %edx
321	shrl %eax
322	movzwl son(%ebx, %ebp), %ecx /* get son of old entry */
323	movl %ecx, %esi
324	addl %esi, %esi
325	movw %ax, parent(%esi, %ebp) /* and update the ptr to new parent */
326	cmpl $TABLESZ, %ecx
327	jae update3 /* do this for both branches */
328	movw %ax, parent+2(%esi, %ebp) /* if not a leaf node */
329	update3:
330	movl %edx, %esi
331	movzwl son(%esi, %ebp), %edx /* get son of new entry */
332	movw %cx, son(%esi, %ebp) /* update its contents */
333	movl %edx, %esi
334	addl %esi, %esi
335	movl %ebx, %ecx
336	shrl %ecx
337	movw %cx, parent(%esi, %ebp) /* and update the ptr to new paren */
338	cmpl $TABLESZ, %edx
339	jae update4 /* do this for both branches */
340	movw %cx, parent+2(%esi, %ebp) /* if not a leaf node */
341	update4:
342	movw %dx, son(%ebx, %ebp) /* update son of old entry */
343	movl %eax, %ebx /* continue with new entry */
344	shll %ebx
345	update5:
346	movzwl parent(%ebx, %ebp), %ebx /* continue with parent */
347	orl %ebx, %ebx
348	jnz update1 /* until we found the root entry */
349	popl %eax
350	popl %esi
351	ret
352
353	/*
354	* constant data. this part of the program resides in ROM and cannot be
355	* changed
356	*
357	* run length encoded tables will be uncompressed into the bss segment
358	* take care with any symbols here for .com files to add 0x100 to address
359	*/
360
361	dcodrle: .byte 0x01,0x03,0x08,0x0C,0x18,0x10
362	dlenrle: .byte 0x20,0x30,0x40,0x30,0x30,0x10
363
364	/*
365	* variable data segment (bss)
366	* this segment will always be found at 0x90000 (i.e. at RELOC - SCRATCH)
367	*
368	* do not change the order or the sizes of any of the following tables
369	* the initialization code makes assumptions on the exact layout of the
370	* data structures...
371	*/
372
373	.bss
374	/* lookup table for index into buffer of recently output characters */
375	dcode: .skip 256
376
377	/* lookup table for length of code sequence from buffer of recent characters */
378	dlen: .skip 256
379
380	/* table with frequency counts for all codes */
381	freq: .skip 2*(TABLESZ+1)
382
383	/* pointer to child nodes */
384	son: .skip 2*(TABLESZ)
385
386	/* the first part of this table contains all the codes (0..TABLESZ-1) */
387	/* the second part contains all leaf nodes (TABLESZ..) */
388	parent: .skip 2*(TABLESZ+NCHAR)
389
390	/* temporary storage for extracting bits from compressed data stream */
391	getlen: .skip 1
392	getbuf: .skip 1
393
394	/* the initial buffer has to be filled with spaces */
395	.balign 4
396	spaces:
397	.skip BUFSZ - LOOKAHEAD
398	/* uncompressed data will be written here */
399	uncompressed:
400

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Original Format