1 #include "boot.h"
2 #include "squeeze.h"
3
4 /*
5 * for details of `unsqueeze' see:
6 *
7 * %A Mark Taunton
8 * %T Compressed Executables: An Exercise in Thinking Small
9 * %P 385-404
10 * %I USENIX
11 * %B USENIX Conference Proceedings
12 * %D Summer 1991
13 * %C Nashville, TN
14 *
15 * several of the unimplemented improvements described in the paper
16 * have been implemented here
17 *
18 * there is a further transformation on the powerpc (QFLAG!=0) to shuffle bits
19 * in certain instructions so as to push the fixed bits to the top of the word.
20 */
21
22 #define EXECHDRLEN (8*4)
23
24 typedef struct Squeeze Squeeze;
25 struct Squeeze {
26 int n;
27 ulong tab[7*256];
28 };
29
30 #define GET4(p) (((((((p)[0]<<8)|(p)[1])<<8)|(p)[2])<<8)|(p)[3])
31
32 /*
33 * for speed of unsqueezing from Flash, certain checks are
34 * not done inside the loop (as they would be in the unsqueeze program zqs),
35 * but instead the checksum is expected to catch corrupted files.
36 * in fact the Squeeze array bounds can't be exceeded in practice
37 * because the tables are always full for a squeezed kernel.
38 */
39 enum {
40 QFLAG = 1, /* invert powerpc-specific code transformation */
41 CHECK = 0, /* check precise bounds in Squeeze array (otherwise checksum detects error) */
42 };
43
44 static ulong chksum;
45 static int rdtab(Block*, Squeeze*, int);
46 static ulong* unsqueeze(ulong*, uchar*, uchar*, Squeeze*, Squeeze*, ulong);
47 static uchar* unsqzseg(uchar*, Block*, long, long, char*);
48 static Alarm* unsqzal;
49
50 int
issqueezed(uchar * b)51 issqueezed(uchar *b)
52 {
53 return GET4(b) == SQMAGIC? GET4(b+SQHDRLEN): 0;
54 }
55
56 static void
unsqzdot(Alarm *)57 unsqzdot(Alarm*)
58 {
59 unsqzal = alarm(500, unsqzdot, nil);
60 print(".");
61 }
62
63 long
unsqueezef(Block * b,ulong * entryp)64 unsqueezef(Block *b, ulong *entryp)
65 {
66 uchar *loada, *wp;
67 ulong toptxt, topdat, oldsum;
68 long asis, nst, nsd;
69 Sqhdr *sqh;
70 Exec *ex;
71
72 if(BLEN(b) < SQHDRLEN+EXECHDRLEN)
73 return -1;
74 sqh = (Sqhdr*)b->rp;
75 if(GET4(sqh->magic) != SQMAGIC)
76 return -1;
77 chksum = 0;
78 toptxt = GET4(sqh->toptxt);
79 topdat = GET4(sqh->topdat);
80 oldsum = GET4(sqh->sum);
81 asis = GET4(sqh->asis);
82 nst = GET4(sqh->text);
83 nsd = GET4(sqh->data);
84 b->rp += SQHDRLEN;
85 ex = (Exec*)b->rp;
86 if(GET4(ex->magic) != Q_MAGIC){
87 print("zqs: not powerPC executable\n");
88 return -1;
89 }
90 *entryp = GET4(ex->entry);
91 b->rp += EXECHDRLEN;
92 loada = KADDR(PADDR(*entryp));
93 wp = unsqzseg(loada, b, nst, toptxt, "text");
94 if(wp == nil){
95 print("zqs: format error\n");
96 return -1;
97 }
98 if(nsd){
99 wp = (uchar*)PGROUND((ulong)wp);
100 wp = unsqzseg(wp, b, nsd, topdat, "data");
101 if(wp == nil){
102 print("zqs: format error\n");
103 return -1;
104 }
105 }
106 if(asis){
107 memmove(wp, b->rp, asis);
108 wp += asis;
109 b->rp += asis;
110 }
111 if(chksum != oldsum){
112 print("\nsqueezed kernel: checksum error: %8.8lux need %8.8lux\n", chksum, oldsum);
113 return -1;
114 }
115 return wp-loada;
116 }
117
118 static uchar *
unsqzseg(uchar * wp,Block * b,long ns,long top,char * what)119 unsqzseg(uchar *wp, Block *b, long ns, long top, char *what)
120 {
121 static Squeeze sq3, sq4;
122
123 print("unpack %s %8.8lux %lud:", what, wp, ns);
124 if(ns == 0)
125 return wp;
126 if(rdtab(b, &sq3, 0) < 0)
127 return nil;
128 if(rdtab(b, &sq4, 8) < 0)
129 return nil;
130 if(BLEN(b) < ns){
131 print(" **size error\n");
132 return nil;
133 }
134 unsqzal = alarm(500, unsqzdot, nil);
135 wp = (uchar*)unsqueeze((ulong*)wp, b->rp, b->rp+ns, &sq3, &sq4, top);
136 cancel(unsqzal);
137 unsqzal = nil;
138 print("\n");
139 if(wp == nil){
140 print("zqs: corrupt squeezed data stream\n");
141 return nil;
142 }
143 b->rp += ns;
144 return wp;
145 }
146
147 static ulong*
unsqueeze(ulong * wp,uchar * rp,uchar * ep,Squeeze * sq3,Squeeze * sq4,ulong top)148 unsqueeze(ulong *wp, uchar *rp, uchar *ep, Squeeze *sq3, Squeeze *sq4, ulong top)
149 {
150 ulong nx, csum;
151 int code, n;
152
153 if(QFLAG){
154 QREMAP(top); /* adjust top just once, outside the loop */
155 }
156 csum = chksum;
157 while(rp < ep){
158 /* no function calls within this loop for speed */
159 code = *rp;
160 rp++;
161 n = 0;
162 nx = code>>4;
163 do{
164 if(nx == 0){
165 nx = top;
166 }else{
167 if(nx==1){
168 nx = (((((rp[3]<<8)|rp[2])<<8)|rp[1])<<8)|rp[0];
169 rp += 4;
170 }else if(nx <= 8){ /* 2 to 8 */
171 nx = ((nx-2)<<8) | rp[0];
172 if(CHECK && nx >= sq4->n)
173 return nil; /* corrupted file */
174 nx = sq4->tab[nx] | rp[1];
175 rp += 2;
176 }else{ /* 9 to 15 */
177 nx = ((nx-9)<<8) | rp[0];
178 if(CHECK && nx >= sq3->n)
179 return nil; /* corrupted file */
180 nx = sq3->tab[nx];
181 rp++;
182 }
183 if(rp > ep)
184 return nil; /* corrupted file */
185 if(QFLAG){
186 QREMAP(nx);
187 }
188 }
189 *wp = nx;
190 wp++;
191 csum += nx;
192 nx = code & 0xF;
193 }while(++n == 1);
194 }
195 chksum = csum;
196 return wp;
197 }
198
199 static int
rdtab(Block * b,Squeeze * sq,int shift)200 rdtab(Block *b, Squeeze *sq, int shift)
201 {
202 uchar *p, *ep;
203 ulong v, w;
204 int i;
205
206 if(BLEN(b) < 2)
207 return -1;
208 i = (b->rp[0]<<8) | b->rp[1];
209 if(1)
210 print(" T%d", i);
211 b->rp += 2;
212 if((i -= 2) > 0){
213 if(BLEN(b) < i)
214 return -1;
215 }
216 sq->n = 0;
217 p = b->rp;
218 ep = b->rp+i;
219 b->rp += i;
220 v = 0;
221 while(p < ep){
222 w = 0;
223 do{
224 if(p >= ep)
225 return -1;
226 w = (w<<7) | (*p & 0x7F);
227 }while(*p++ & 0x80);
228 v += w;
229 if(0)
230 print("%d %8.8lux %8.8lux\n", sq->n, v, w);
231 sq->tab[sq->n++] = v<<shift;
232 }
233 return 0;
234 }
235