1
2 /*-------------------------------------------------------------*/
3 /*--- Decompression machinery ---*/
4 /*--- decompress.c ---*/
5 /*-------------------------------------------------------------*/
6
7 /*--
8 This file is a part of bzip2 and/or libbzip2, a program and
9 library for lossless, block-sorting data compression.
10
11 Copyright (C) 1996-1999 Julian R Seward. All rights reserved.
12
13 Redistribution and use in source and binary forms, with or without
14 modification, are permitted provided that the following conditions
15 are met:
16
17 1. Redistributions of source code must retain the above copyright
18 notice, this list of conditions and the following disclaimer.
19
20 2. The origin of this software must not be misrepresented; you must
21 not claim that you wrote the original software. If you use this
22 software in a product, an acknowledgment in the product
23 documentation would be appreciated but is not required.
24
25 3. Altered source versions must be plainly marked as such, and must
26 not be misrepresented as being the original software.
27
28 4. The name of the author may not be used to endorse or promote
29 products derived from this software without specific prior written
30 permission.
31
32 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
33 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
34 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
35 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
36 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
37 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
38 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
39 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
40 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
41 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
42 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
43
44 Julian Seward, Cambridge, UK.
45 jseward@acm.org
46 bzip2/libbzip2 version 0.9.5 of 24 May 1999
47
48 This program is based on (at least) the work of:
49 Mike Burrows
50 David Wheeler
51 Peter Fenwick
52 Alistair Moffat
53 Radford Neal
54 Ian H. Witten
55 Robert Sedgewick
56 Jon L. Bentley
57
58 For more information on these sources, see the manual.
59 --*/
60
61
62 #include "stdafx.h"
63
64
65 /*---------------------------------------------------*/
66 static
makeMaps_d(DState * s)67 void makeMaps_d ( DState* s )
68 {
69 Int32 i;
70 s->nInUse = 0;
71 for (i = 0; i < 256; i++)
72 if (s->inUse[i]) {
73 s->seqToUnseq[s->nInUse] = i;
74 s->nInUse++;
75 }
76 }
77
78
79 /*---------------------------------------------------*/
80 #define RETURN(rrr) \
81 { retVal = rrr; goto save_state_and_return; };
82
83 #define GET_BITS(lll,vvv,nnn) \
84 case lll: s->state = lll; \
85 while (True) { \
86 if (s->bsLive >= nnn) { \
87 UInt32 v; \
88 v = (s->bsBuff >> \
89 (s->bsLive-nnn)) & ((1 << nnn)-1); \
90 s->bsLive -= nnn; \
91 vvv = v; \
92 break; \
93 } \
94 if (s->strm->avail_in == 0) RETURN(BZ_OK); \
95 s->bsBuff \
96 = (s->bsBuff << 8) | \
97 ((UInt32) \
98 (*((UChar*)(s->strm->next_in)))); \
99 s->bsLive += 8; \
100 s->strm->next_in++; \
101 s->strm->avail_in--; \
102 s->strm->total_in++; \
103 }
104
105 #define GET_UCHAR(lll,uuu) \
106 GET_BITS(lll,uuu,8)
107
108 #define GET_BIT(lll,uuu) \
109 GET_BITS(lll,uuu,1)
110
111 /*---------------------------------------------------*/
112 #define GET_MTF_VAL(label1,label2,lval) \
113 { \
114 if (groupPos == 0) { \
115 groupNo++; \
116 groupPos = BZ_G_SIZE; \
117 gSel = s->selector[groupNo]; \
118 gMinlen = s->minLens[gSel]; \
119 gLimit = &(s->limit[gSel][0]); \
120 gPerm = &(s->perm[gSel][0]); \
121 gBase = &(s->base[gSel][0]); \
122 } \
123 groupPos--; \
124 zn = gMinlen; \
125 GET_BITS(label1, zvec, zn); \
126 while (zvec > gLimit[zn]) { \
127 zn++; \
128 GET_BIT(label2, zj); \
129 zvec = (zvec << 1) | zj; \
130 }; \
131 lval = gPerm[zvec - gBase[zn]]; \
132 }
133
134
135 /*---------------------------------------------------*/
decompress(DState * s)136 Int32 decompress ( DState* s )
137 {
138 UChar uc;
139 Int32 retVal;
140 Int32 minLen, maxLen;
141 bz_stream* strm = s->strm;
142
143 /* stuff that needs to be saved/restored */
144 Int32 i;
145 Int32 j;
146 Int32 t;
147 Int32 alphaSize;
148 Int32 nGroups;
149 Int32 nSelectors;
150 Int32 EOB;
151 Int32 groupNo;
152 Int32 groupPos;
153 Int32 nextSym;
154 Int32 nblockMAX;
155 Int32 nblock;
156 Int32 es;
157 Int32 N;
158 Int32 curr;
159 Int32 zt;
160 Int32 zn;
161 Int32 zvec;
162 Int32 zj;
163 Int32 gSel;
164 Int32 gMinlen;
165 Int32* gLimit;
166 Int32* gBase;
167 Int32* gPerm;
168
169 if (s->state == BZ_X_MAGIC_1) {
170 /*initialise the save area*/
171 s->save_i = 0;
172 s->save_j = 0;
173 s->save_t = 0;
174 s->save_alphaSize = 0;
175 s->save_nGroups = 0;
176 s->save_nSelectors = 0;
177 s->save_EOB = 0;
178 s->save_groupNo = 0;
179 s->save_groupPos = 0;
180 s->save_nextSym = 0;
181 s->save_nblockMAX = 0;
182 s->save_nblock = 0;
183 s->save_es = 0;
184 s->save_N = 0;
185 s->save_curr = 0;
186 s->save_zt = 0;
187 s->save_zn = 0;
188 s->save_zvec = 0;
189 s->save_zj = 0;
190 s->save_gSel = 0;
191 s->save_gMinlen = 0;
192 s->save_gLimit = NULL;
193 s->save_gBase = NULL;
194 s->save_gPerm = NULL;
195 }
196
197 /*restore from the save area*/
198 i = s->save_i;
199 j = s->save_j;
200 t = s->save_t;
201 alphaSize = s->save_alphaSize;
202 nGroups = s->save_nGroups;
203 nSelectors = s->save_nSelectors;
204 EOB = s->save_EOB;
205 groupNo = s->save_groupNo;
206 groupPos = s->save_groupPos;
207 nextSym = s->save_nextSym;
208 nblockMAX = s->save_nblockMAX;
209 nblock = s->save_nblock;
210 es = s->save_es;
211 N = s->save_N;
212 curr = s->save_curr;
213 zt = s->save_zt;
214 zn = s->save_zn;
215 zvec = s->save_zvec;
216 zj = s->save_zj;
217 gSel = s->save_gSel;
218 gMinlen = s->save_gMinlen;
219 gLimit = s->save_gLimit;
220 gBase = s->save_gBase;
221 gPerm = s->save_gPerm;
222
223 retVal = BZ_OK;
224
225 switch (s->state) {
226
227 GET_UCHAR(BZ_X_MAGIC_1, uc);
228 if (uc != 'B') RETURN(BZ_DATA_ERROR_MAGIC);
229
230 GET_UCHAR(BZ_X_MAGIC_2, uc);
231 if (uc != 'Z') RETURN(BZ_DATA_ERROR_MAGIC);
232
233 GET_UCHAR(BZ_X_MAGIC_3, uc)
234 if (uc != 'h') RETURN(BZ_DATA_ERROR_MAGIC);
235
236 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
237 if (s->blockSize100k < '1' ||
238 s->blockSize100k > '9') RETURN(BZ_DATA_ERROR_MAGIC);
239 s->blockSize100k -= '0';
240
241 if (s->smallDecompress) {
242 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
243 s->ll4 = BZALLOC(
244 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
245 );
246 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
247 } else {
248 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
249 if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
250 }
251
252 GET_UCHAR(BZ_X_BLKHDR_1, uc);
253
254 if (uc == 0x17) goto endhdr_2;
255 if (uc != 0x31) RETURN(BZ_DATA_ERROR);
256 GET_UCHAR(BZ_X_BLKHDR_2, uc);
257 if (uc != 0x41) RETURN(BZ_DATA_ERROR);
258 GET_UCHAR(BZ_X_BLKHDR_3, uc);
259 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
260 GET_UCHAR(BZ_X_BLKHDR_4, uc);
261 if (uc != 0x26) RETURN(BZ_DATA_ERROR);
262 GET_UCHAR(BZ_X_BLKHDR_5, uc);
263 if (uc != 0x53) RETURN(BZ_DATA_ERROR);
264 GET_UCHAR(BZ_X_BLKHDR_6, uc);
265 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
266
267 s->currBlockNo++;
268 if (s->verbosity >= 2)
269 VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
270
271 s->storedBlockCRC = 0;
272 GET_UCHAR(BZ_X_BCRC_1, uc);
273 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
274 GET_UCHAR(BZ_X_BCRC_2, uc);
275 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
276 GET_UCHAR(BZ_X_BCRC_3, uc);
277 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
278 GET_UCHAR(BZ_X_BCRC_4, uc);
279 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
280
281 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
282
283 s->origPtr = 0;
284 GET_UCHAR(BZ_X_ORIGPTR_1, uc);
285 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
286 GET_UCHAR(BZ_X_ORIGPTR_2, uc);
287 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
288 GET_UCHAR(BZ_X_ORIGPTR_3, uc);
289 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
290
291 /*--- Receive the mapping table ---*/
292 for (i = 0; i < 16; i++) {
293 GET_BIT(BZ_X_MAPPING_1, uc);
294 if (uc == 1)
295 s->inUse16[i] = True; else
296 s->inUse16[i] = False;
297 }
298
299 for (i = 0; i < 256; i++) s->inUse[i] = False;
300
301 for (i = 0; i < 16; i++)
302 if (s->inUse16[i])
303 for (j = 0; j < 16; j++) {
304 GET_BIT(BZ_X_MAPPING_2, uc);
305 if (uc == 1) s->inUse[i * 16 + j] = True;
306 }
307 makeMaps_d ( s );
308 alphaSize = s->nInUse+2;
309
310 /*--- Now the selectors ---*/
311 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
312 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
313 for (i = 0; i < nSelectors; i++) {
314 j = 0;
315 while (True) {
316 GET_BIT(BZ_X_SELECTOR_3, uc);
317 if (uc == 0) break;
318 j++;
319 if (j > 5) RETURN(BZ_DATA_ERROR);
320 }
321 s->selectorMtf[i] = j;
322 }
323
324 /*--- Undo the MTF values for the selectors. ---*/
325 {
326 UChar pos[BZ_N_GROUPS], tmp, v;
327 for (v = 0; v < nGroups; v++) pos[v] = v;
328
329 for (i = 0; i < nSelectors; i++) {
330 v = s->selectorMtf[i];
331 tmp = pos[v];
332 while (v > 0) { pos[v] = pos[v-1]; v--; }
333 pos[0] = tmp;
334 s->selector[i] = tmp;
335 }
336 }
337
338 /*--- Now the coding tables ---*/
339 for (t = 0; t < nGroups; t++) {
340 GET_BITS(BZ_X_CODING_1, curr, 5);
341 for (i = 0; i < alphaSize; i++) {
342 while (True) {
343 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
344 GET_BIT(BZ_X_CODING_2, uc);
345 if (uc == 0) break;
346 GET_BIT(BZ_X_CODING_3, uc);
347 if (uc == 0) curr++; else curr--;
348 }
349 s->len[t][i] = curr;
350 }
351 }
352
353 /*--- Create the Huffman decoding tables ---*/
354 for (t = 0; t < nGroups; t++) {
355 minLen = 32;
356 maxLen = 0;
357 for (i = 0; i < alphaSize; i++) {
358 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
359 if (s->len[t][i] < minLen) minLen = s->len[t][i];
360 }
361 hbCreateDecodeTables (
362 &(s->limit[t][0]),
363 &(s->base[t][0]),
364 &(s->perm[t][0]),
365 &(s->len[t][0]),
366 minLen, maxLen, alphaSize
367 );
368 s->minLens[t] = minLen;
369 }
370
371 /*--- Now the MTF values ---*/
372
373 EOB = s->nInUse+1;
374 nblockMAX = 100000 * s->blockSize100k;
375 groupNo = -1;
376 groupPos = 0;
377
378 for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
379
380 /*-- MTF init --*/
381 {
382 Int32 ii, jj, kk;
383 kk = MTFA_SIZE-1;
384 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
385 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
386 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
387 kk--;
388 }
389 s->mtfbase[ii] = kk + 1;
390 }
391 }
392 /*-- end MTF init --*/
393
394 nblock = 0;
395
396 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
397
398 while (True) {
399
400 if (nextSym == EOB) break;
401
402 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
403
404 es = -1;
405 N = 1;
406 do {
407 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
408 if (nextSym == BZ_RUNB) es = es + (1+1) * N;
409 N = N * 2;
410 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
411 }
412 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
413
414 es++;
415 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
416 s->unzftab[uc] += es;
417
418 if (s->smallDecompress)
419 while (es > 0) {
420 s->ll16[nblock] = (UInt16)uc;
421 nblock++;
422 es--;
423 }
424 else
425 while (es > 0) {
426 s->tt[nblock] = (UInt32)uc;
427 nblock++;
428 es--;
429 };
430
431 if (nblock > nblockMAX) RETURN(BZ_DATA_ERROR);
432 continue;
433
434 } else {
435
436 if (nblock > nblockMAX) RETURN(BZ_DATA_ERROR);
437
438 /*-- uc = MTF ( nextSym-1 ) --*/
439 {
440 Int32 ii, jj, kk, pp, lno, off;
441 UInt32 nn;
442 nn = (UInt32)(nextSym - 1);
443
444 if (nn < MTFL_SIZE) {
445 /* avoid general-case expense */
446 pp = s->mtfbase[0];
447 uc = s->mtfa[pp+nn];
448 while (nn > 3) {
449 Int32 z = pp+nn;
450 s->mtfa[(z) ] = s->mtfa[(z)-1];
451 s->mtfa[(z)-1] = s->mtfa[(z)-2];
452 s->mtfa[(z)-2] = s->mtfa[(z)-3];
453 s->mtfa[(z)-3] = s->mtfa[(z)-4];
454 nn -= 4;
455 }
456 while (nn > 0) {
457 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
458 };
459 s->mtfa[pp] = uc;
460 } else {
461 /* general case */
462 lno = nn / MTFL_SIZE;
463 off = nn % MTFL_SIZE;
464 pp = s->mtfbase[lno] + off;
465 uc = s->mtfa[pp];
466 while (pp > s->mtfbase[lno]) {
467 s->mtfa[pp] = s->mtfa[pp-1]; pp--;
468 };
469 s->mtfbase[lno]++;
470 while (lno > 0) {
471 s->mtfbase[lno]--;
472 s->mtfa[s->mtfbase[lno]]
473 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
474 lno--;
475 }
476 s->mtfbase[0]--;
477 s->mtfa[s->mtfbase[0]] = uc;
478 if (s->mtfbase[0] == 0) {
479 kk = MTFA_SIZE-1;
480 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
481 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
482 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
483 kk--;
484 }
485 s->mtfbase[ii] = kk + 1;
486 }
487 }
488 }
489 }
490 /*-- end uc = MTF ( nextSym-1 ) --*/
491
492 s->unzftab[s->seqToUnseq[uc]]++;
493 if (s->smallDecompress)
494 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
495 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);
496 nblock++;
497
498 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
499 continue;
500 }
501 }
502
503 s->state_out_len = 0;
504 s->state_out_ch = 0;
505 BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
506 s->state = BZ_X_OUTPUT;
507 if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
508
509 /*-- Set up cftab to facilitate generation of T^(-1) --*/
510 s->cftab[0] = 0;
511 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
512 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
513
514 if (s->smallDecompress) {
515
516 /*-- Make a copy of cftab, used in generation of T --*/
517 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
518
519 /*-- compute the T vector --*/
520 for (i = 0; i < nblock; i++) {
521 uc = (UChar)(s->ll16[i]);
522 SET_LL(i, s->cftabCopy[uc]);
523 s->cftabCopy[uc]++;
524 }
525
526 /*-- Compute T^(-1) by pointer reversal on T --*/
527 i = s->origPtr;
528 j = GET_LL(i);
529 do {
530 Int32 tmp = GET_LL(j);
531 SET_LL(j, i);
532 i = j;
533 j = tmp;
534 }
535 while (i != s->origPtr);
536
537 s->tPos = s->origPtr;
538 s->nblock_used = 0;
539 if (s->blockRandomised) {
540 BZ_RAND_INIT_MASK;
541 BZ_GET_SMALL(s->k0); s->nblock_used++;
542 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
543 } else {
544 BZ_GET_SMALL(s->k0); s->nblock_used++;
545 }
546
547 } else {
548
549 /*-- compute the T^(-1) vector --*/
550 for (i = 0; i < nblock; i++) {
551 uc = (UChar)(s->tt[i] & 0xff);
552 s->tt[s->cftab[uc]] |= (i << 8);
553 s->cftab[uc]++;
554 }
555
556 s->tPos = s->tt[s->origPtr] >> 8;
557 s->nblock_used = 0;
558 if (s->blockRandomised) {
559 BZ_RAND_INIT_MASK;
560 BZ_GET_FAST(s->k0); s->nblock_used++;
561 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
562 } else {
563 BZ_GET_FAST(s->k0); s->nblock_used++;
564 }
565
566 }
567
568 RETURN(BZ_OK);
569
570
571
572 endhdr_2:
573
574 GET_UCHAR(BZ_X_ENDHDR_2, uc);
575 if (uc != 0x72) RETURN(BZ_DATA_ERROR);
576 GET_UCHAR(BZ_X_ENDHDR_3, uc);
577 if (uc != 0x45) RETURN(BZ_DATA_ERROR);
578 GET_UCHAR(BZ_X_ENDHDR_4, uc);
579 if (uc != 0x38) RETURN(BZ_DATA_ERROR);
580 GET_UCHAR(BZ_X_ENDHDR_5, uc);
581 if (uc != 0x50) RETURN(BZ_DATA_ERROR);
582 GET_UCHAR(BZ_X_ENDHDR_6, uc);
583 if (uc != 0x90) RETURN(BZ_DATA_ERROR);
584
585 s->storedCombinedCRC = 0;
586 GET_UCHAR(BZ_X_CCRC_1, uc);
587 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
588 GET_UCHAR(BZ_X_CCRC_2, uc);
589 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
590 GET_UCHAR(BZ_X_CCRC_3, uc);
591 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
592 GET_UCHAR(BZ_X_CCRC_4, uc);
593 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
594
595 s->state = BZ_X_IDLE;
596 RETURN(BZ_STREAM_END);
597
598 default: AssertH ( False, 4001 );
599 }
600
601 AssertH ( False, 4002 );
602
603 save_state_and_return:
604
605 s->save_i = i;
606 s->save_j = j;
607 s->save_t = t;
608 s->save_alphaSize = alphaSize;
609 s->save_nGroups = nGroups;
610 s->save_nSelectors = nSelectors;
611 s->save_EOB = EOB;
612 s->save_groupNo = groupNo;
613 s->save_groupPos = groupPos;
614 s->save_nextSym = nextSym;
615 s->save_nblockMAX = nblockMAX;
616 s->save_nblock = nblock;
617 s->save_es = es;
618 s->save_N = N;
619 s->save_curr = curr;
620 s->save_zt = zt;
621 s->save_zn = zn;
622 s->save_zvec = zvec;
623 s->save_zj = zj;
624 s->save_gSel = gSel;
625 s->save_gMinlen = gMinlen;
626 s->save_gLimit = gLimit;
627 s->save_gBase = gBase;
628 s->save_gPerm = gPerm;
629
630 return retVal;
631 }
632
633
634 /*-------------------------------------------------------------*/
635 /*--- end decompress.c ---*/
636 /*-------------------------------------------------------------*/
637