OpenCores
URL https://opencores.org/ocsvn/hdl-deflate/hdl-deflate/trunk

Subversion Repositories hdl-deflate

[/] [hdl-deflate/] [trunk/] [deflate.py] - Blame information for rev 4

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 2 tomtor
"""
2
MyHDL FPGA Deflate (de)compressor, see RFC 1950/1951
3
 
4
Copyright 2018 by Tom Vijlbrief
5
 
6
See: https://github.com/tomtor
7
 
8
This MyHDL FPGA implementation is partially inspired by the C++ implementation
9
from https://create.stephan-brumme.com/deflate-decoder
10
 
11
"""
12
 
13
from math import log2
14
 
15
from myhdl import always, block, Signal, intbv, Error, ResetSignal, \
16
    enum, always_seq, always_comb, concat, ConcatSignal, modbv
17
 
18
IDLE, RESET, WRITE, READ, STARTC, STARTD = range(6)
19
 
20
CWINDOW = 32    # Search window for compression
21
 
22
OBSIZE = 8192   # Size of output buffer (BRAM)
23
IBSIZE = 4 * CWINDOW  # 2048   # Size of input buffer (LUT-RAM)
24
 
25
if OBSIZE > IBSIZE:
26
    LBSIZE = log2(OBSIZE)
27
else:
28
    LBSIZE = log2(IBSIZE)
29
 
30
IBS = (1 << int(log2(IBSIZE))) - 1
31
 
32
d_state = enum('IDLE', 'HEADER', 'BL', 'READBL', 'REPEAT', 'DISTTREE', 'INIT3',
33
               'HF1', 'HF1INIT', 'HF2', 'HF3', 'HF4', 'HF4_2', 'HF4_3',
34
               'STATIC', 'D_NEXT', 'D_NEXT_2',
35
               'D_INFLATE', 'SPREAD', 'NEXT', 'INFLATE', 'COPY', 'CSTATIC',
36
               'SEARCH', 'DISTANCE', 'CHECKSUM') # , encoding='one_hot')
37
 
38
CodeLengthOrder = (16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14,
39
                   1, 15)
40
 
41
CopyLength = (3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35,
42
              43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258)
43
 
44
ExtraLengthBits = (0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
45
                   3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0)
46
 
47
CopyDistance = (1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
48
                257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193,
49
                12289, 16385, 24577)
50
 
51
ExtraDistanceBits = (0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
52
 
53
 
54
@block
55
def deflate(i_mode, o_done, i_data, o_iprogress, o_oprogress, o_byte, i_addr,
56
            clk, reset):
57
 
58
    """ Deflate (de)compress
59
 
60
    Ports:
61
 
62
    """
63
 
64
    iram = [Signal(intbv()[8:]) for _ in range(IBSIZE)]
65
    oram = [Signal(intbv()[8:]) for _ in range(OBSIZE)]
66
 
67
    oaddr = Signal(intbv()[LBSIZE:])
68
    oraddr = Signal(intbv()[LBSIZE:])
69
    obyte = Signal(intbv()[8:])
70
    orbyte = Signal(intbv()[8:])
71
 
72
    isize = Signal(intbv()[LBSIZE:])
73
    state = Signal(d_state.IDLE)
74
    method = Signal(intbv()[3:])
75
    final = Signal(bool())
76
    do_compress = Signal(bool())
77
 
78
    numLiterals = Signal(intbv()[9:])
79
    numDistance = Signal(intbv()[6:])
80
    numCodeLength = Signal(intbv()[9:])
81
    b_numCodeLength = Signal(intbv()[9:])
82
 
83
    CodeLengths = 19
84
    MaxCodeLength = 15
85
    InstantMaxBit = 10
86
    EndOfBlock = 256
87
    MaxBitLength = 288
88
    # MaxToken = 285
89
    InvalidToken = 300
90
 
91
    CODEBITS = 10 # MaxCodeLength
92
    BITBITS = 9
93
 
94
    codeLength = [Signal(intbv()[4:]) for _ in range(MaxBitLength+2)]
95
    bits = Signal(intbv()[4:])
96
    bitLengthCount = [Signal(intbv()[9:]) for _ in range(MaxCodeLength+1)]
97
    nextCode = [Signal(intbv()[CODEBITS:]) for _ in range(MaxCodeLength)]
98
    reverse = Signal(intbv()[CODEBITS:])
99
    code_bits = [Signal(intbv()[9:]) for _ in range(MaxBitLength)]
100
    distanceLength = [Signal(intbv()[4:]) for _ in range(32)]
101
 
102
    leaves = [Signal(intbv()[CODEBITS + BITBITS:]) for _ in range(512)]
103
    lwaddr = Signal(intbv()[9:])
104
    # lraddr = Signal(intbv()[9:])
105
    d_leaves = [Signal(intbv()[CODEBITS + BITBITS:]) for _ in range(128)]
106
    # rleaf = Signal(intbv()[CODEBITS + BITBITS:])
107
    wleaf = Signal(intbv()[CODEBITS + BITBITS:])
108
    leaf = Signal(intbv()[CODEBITS + BITBITS:])
109
 
110
    minBits = Signal(intbv()[5:])
111
    maxBits = Signal(intbv()[5:])
112
    d_maxBits = Signal(intbv()[5:])
113
    instantMaxBit = Signal(intbv()[InstantMaxBit:])
114
    d_instantMaxBit = Signal(intbv()[InstantMaxBit:])
115
    instantMask = Signal(intbv()[MaxCodeLength:])
116
    d_instantMask = Signal(intbv()[MaxCodeLength:])
117
    spread = Signal(intbv()[10:])
118
    step = Signal(intbv()[10:])
119
 
120
    static = Signal(bool())
121
 
122
    code = Signal(intbv()[15:])
123
    lastToken = Signal(intbv()[15:])
124
    howOften = Signal(intbv()[9:])
125
 
126
    cur_i = Signal(intbv()[LBSIZE:])
127
    spread_i = Signal(intbv()[9:])
128
    cur_HF1 = Signal(intbv()[10:])
129
    cur_static = Signal(intbv()[9:])
130
    cur_cstatic = Signal(intbv()[LBSIZE:])
131
    cur_search = Signal(intbv(min=-CWINDOW,max=IBSIZE))
132
    cur_dist = Signal(intbv(min=-CWINDOW,max=IBSIZE))
133
    # cur_next = Signal(intbv()[5:])
134
    cur_next = Signal(bool())
135
 
136
    length = Signal(intbv()[LBSIZE:])
137
    offset = Signal(intbv()[LBSIZE:])
138
 
139
    di = Signal(intbv()[LBSIZE:])
140
    old_di = Signal(intbv()[LBSIZE:])
141
    dio = Signal(intbv()[3:])
142
    do = Signal(intbv()[LBSIZE:])
143
    doo = Signal(intbv()[3:])
144
 
145
    b1 = Signal(intbv()[8:])
146
    b2 = Signal(intbv()[8:])
147
    b3 = Signal(intbv()[8:])
148
    b4 = Signal(intbv()[8:])
149
 
150
    b41 = ConcatSignal(b4, b3, b2, b1)
151
    b41._markUsed()
152
 
153
    nb = Signal(intbv()[3:])
154
 
155
    filled = Signal(bool())
156
 
157
    ob1 = Signal(intbv()[8:])
158
    copy1 = Signal(intbv()[8:])
159 4 tomtor
    copy2 = Signal(intbv()[8:])
160 2 tomtor
    flush = Signal(bool(0))
161
 
162
    adler1 = Signal(intbv()[16:])
163
    adler2 = Signal(intbv()[16:])
164
    ladler1 = Signal(intbv()[16:])
165
 
166
 
167
    @always(clk.posedge)
168
    def oramwrite():
169
        oram[oaddr].next = obyte
170
        leaves[lwaddr].next = wleaf
171
 
172
    @always(clk.posedge)
173
    def oramread():
174
        orbyte.next = oram[oraddr]
175
        # rleaf.next = leaves[lraddr]
176
 
177
    @always(clk.posedge)
178
    def fill_buf():
179
        if not reset:
180
            print("FILL RESET")
181
            nb.next = 0
182
            b1.next = 0
183
            b2.next = 0
184
            b3.next = 0
185
            b4.next = 0
186
        else:
187
            if isize < 4:
188
                pass
189
            elif i_mode == STARTC or i_mode == STARTD:
190
                nb.next = 0
191
            else:
192
                # print("FILL", di, isize)
193
                nb.next = 4
194
                b1.next = iram[di & IBS]
195
                b2.next = iram[di+1 & IBS]
196
                b3.next = iram[di+2 & IBS]
197
                b4.next = iram[di+3 & IBS]
198
    """
199
    @always(clk.posedge)
200
    def fill_buf():
201
        if not reset:
202
            print("FILL RESET")
203
            nb.next = 0
204
            old_di.next = 0
205
            b1.next = 0
206
            b2.next = 0
207
            b3.next = 0
208
            b4.next = 0
209
        else:
210
            if isize < 4:
211
                pass
212
            elif i_mode == STARTC or i_mode == STARTD:
213
                nb.next = 0
214
            elif not filled and nb == 4 and di - old_di <= 4:
215
                delta = di - old_di
216
                if delta == 1:
217
                    # print("delta == 1")
218
                    b1.next = b2
219
                    b2.next = b3
220
                    b3.next = b4
221
                    b4.next = iram[di+3 & IBS]
222
                    # nb.next = 4
223
                elif delta == 2:
224
                    b1.next = b3
225
                    b2.next = b4
226
                    b3.next = iram[di+2 & IBS]
227
                    nb.next = 3
228
                elif delta == 3:
229
                    b1.next = b4
230
                    b2.next = iram[di+1 & IBS]
231
                    nb.next = 2
232
                elif delta == 4:
233
                    b1.next = iram[di & IBS]
234
                    nb.next = 1
235
                else:
236
                    pass
237
            elif not filled or nb == 0:
238
                # print("nb.next = 1")
239
                b1.next = iram[di & IBS]
240
                nb.next = 1
241
            elif not filled or nb == 1:
242
                b2.next = iram[di+1 & IBS]
243
                nb.next = 2
244
            elif not filled or nb == 2:
245
                b3.next = iram[di+2 & IBS]
246
                nb.next = 3
247
            elif not filled or nb == 3:
248
                b4.next = iram[di+3 & IBS]
249
                nb.next = 4
250
            else:
251
                pass
252
            old_di.next = di
253
    """
254
 
255
    def get4(boffset, width):
256
        if nb != 4:
257
            print("----NB----")
258
            raise Error("NB")
259
        return (b41 >> (dio + boffset)) & ((1 << width) - 1)
260
        # return b41[dio + boffset + width: dio + boffset]
261
 
262
    def adv(width):
263
        # print("adv", width, di, dio, do, doo)
264
        nshift = ((dio + width) >> 3)
265
        # print("nshift: ", nshift)
266
 
267
        o_iprogress.next = di
268
        dio.next = (dio + width) & 0x7
269
        di.next = di + nshift
270
 
271
        if nshift != 0:
272
            filled.next = False
273
 
274
    def put(d, width):
275
        if width > 9:
276
            raise Error("width > 9")
277
        if d > ((1 << width) - 1):
278
            raise Error("too big")
279
        # print("put:", d, width, do, doo, ob1, (ob1 | (d << doo)))
280
        return (ob1 | (d << doo)) & 0xFF
281
 
282
    def put_adv(d, width):
283
        if width > 9:
284
            raise Error("width > 9")
285
        if d > ((1 << width) - 1):
286
            raise Error("too big")
287
        # print("put_adv:", d, width, do, doo, di, dio)
288
        pshift = (doo + width) > 8
289
        # print("pshift: ", pshift)
290
        if pshift:
291
            carry = width - (8 - doo)
292
            # print("carry:", carry, d >> (8 - carry))
293
            ob1.next = d >> (width - carry)
294
        else:
295
            # print("put_adv:", ob1, d, doo)
296
            ob1.next = ob1 | (d << doo)
297
            # print("ob1.next", ob1 | (d << doo))
298
        do.next = do + pshift
299
        o_oprogress.next = do + pshift
300
        doo_next = (doo + width) & 0x7
301
        if doo_next == 0:
302
            flush.next = True
303
        doo.next = doo_next
304
 
305
    def do_flush():
306
        # print("FLUSH")
307
        flush.next = False
308
        ob1.next = 0
309
        o_oprogress.next = do + 1
310
        do.next = do + 1
311
 
312
    def rev_bits(b, nb):
313
        if b >= 1 << nb:
314
            raise Error("too few bits")
315
            print("too few bits")
316
        r = (((b >> 14) & 0x1) << 0) | (((b >> 13) & 0x1) << 1) | \
317
            (((b >> 12) & 0x1) << 2) | (((b >> 11) & 0x1) << 3) | \
318
            (((b >> 10) & 0x1) << 4) | (((b >> 9) & 0x1) << 5) | \
319
            (((b >> 8) & 0x1) << 6) | (((b >> 7) & 0x1) << 7) | \
320
            (((b >> 6) & 0x1) << 8) | (((b >> 5) & 0x1) << 9) | \
321
            (((b >> 4) & 0x1) << 10) | (((b >> 3) & 0x1) << 11) | \
322
            (((b >> 2) & 0x1) << 12) | (((b >> 1) & 0x1) << 13) | \
323
            (((b >> 0) & 0x1) << 14)
324
        r >>= (15 - nb)
325
        return r
326
 
327
    def makeLeaf(lcode, lbits):
328
        if lcode >= 1 << CODEBITS:
329
            raise Error("code too big")
330
        if lbits >= 1 << BITBITS:
331
            raise Error("bits too big")
332
        return (lcode << BITBITS) | lbits
333
 
334
    def get_bits(aleaf):
335
        return aleaf & ((1 << BITBITS) - 1)
336
 
337
    def get_code(aleaf):
338
        return (aleaf >> BITBITS)  # & ((1 << CODEBITS) - 1)
339
 
340
    @always(clk.posedge)
341
    def io_logic():
342
        if i_mode == WRITE:
343
 
344
            # print("WRITE:", i_addr, i_data)
345
            iram[i_addr & IBS].next = i_data
346
            isize.next = i_addr
347
 
348
        elif i_mode == READ:
349
 
350
            # o_data.next = oram[i_addr]
351
            # oraddr.next = i_addr
352
            o_byte.next = oram[i_addr]
353
 
354
        else:
355
            pass
356
 
357
    @always(clk.posedge)
358
    def logic():
359
        if not reset:
360
            print("DEFLATE RESET")
361
            state.next = d_state.IDLE
362
            o_done.next = False
363
            # oaddr.next = 0
364
            # obyte.next = 0
365
        else:
366
 
367
            if state == d_state.IDLE:
368
 
369
                if i_mode == STARTC:
370
 
371
                    print("STARTC")
372
                    do_compress.next = True
373
                    method.next = 1
374
                    o_done.next = False
375
                    o_iprogress.next = 0
376
                    o_oprogress.next = 0
377
                    di.next = 0
378
                    dio.next = 0
379
                    do.next = 0
380
                    doo.next = 0
381
                    filled.next = True
382
                    cur_static.next = 0
383
                    state.next = d_state.STATIC
384
 
385
                elif i_mode == STARTD:
386
 
387
                    do_compress.next = False
388
                    o_done.next = False
389
                    o_iprogress.next = 0
390
                    o_oprogress.next = 0
391
                    di.next = 0
392
                    dio.next = 0
393
                    # oaddr.next = 0
394
                    do.next = 0
395
                    doo.next = 0
396
                    filled.next = True
397
                    state.next = d_state.HEADER
398
 
399
                else:
400
                    pass
401
 
402
            elif state == d_state.HEADER:
403
 
404
                if not filled:
405
                    filled.next = True
406
                elif nb < 4:
407
                    pass
408
                # Read block header
409
                elif di == 0:
410
                    #print(iram[di & IBS])
411
                    #if iram[di & IBS] == 0x78:
412
                    if b1 == 0x78:
413
                        print("deflate mode")
414
                    else:
415
                        print(di, dio, nb, b1, b2, b3, b4, isize)
416
                        raise Error("unexpected mode")
417
                        o_done.next = True
418
                        state.next = d_state.IDLE
419
                    adv(16)
420
                else:
421
                    if get4(0, 1):
422
                        print("final")
423
                        final.next = True
424
                    hm = get4(1, 2)
425
                    method.next = hm
426
                    print("method", hm)
427
                    # print(di, dio, nb, b1, b2, b3, b4, hm, isize)
428
                    if hm == 2:
429
                        state.next = d_state.BL
430
                        numCodeLength.next = 0
431
                        numLiterals.next = 0
432
                        static.next = False
433
                        adv(3)
434
                    elif hm == 1:
435
                        static.next = True
436
                        cur_static.next = 0
437
                        state.next = d_state.STATIC
438
                        adv(3)
439
                    elif hm == 0:
440
                        state.next = d_state.COPY
441
                        skip = 8 - dio
442
                        if skip <= 2:
443
                            skip = 16 - dio
444
                        length.next = get4(skip, 16)
445
                        adv(skip + 16)
446
                        cur_i.next = 0
447
                        offset.next = 7
448
                    else:
449
                        state.next = d_state.IDLE
450
                        print("Bad method")
451
                        raise Error("Bad method")
452
 
453
            elif state == d_state.CSTATIC:
454
 
455
                # print("CSTATIC", cur_i, ob1, do, doo, isize)
456
 
457
                no_adv = 0
458
                if not filled:
459
                    no_adv = 1
460
                    filled.next = True
461
                elif nb < 4:
462
                    no_adv = 1
463
                    pass
464
                elif cur_cstatic == 0:
465
                    flush.next = False
466
                    ob1.next = 0
467
                    adler1.next = 1
468
                    adler2.next = 0
469
                    ladler1.next = 0
470
                    oaddr.next = 0
471
                    obyte.next = 0x78
472
                elif cur_cstatic == 1:
473
                    oaddr.next = 1
474
                    obyte.next = 0x9c
475
                    do.next = 2
476
                elif cur_cstatic == 2:
477
                    oaddr.next = do
478
                    obyte.next = put(0x3, 3)
479
                    put_adv(0x3, 3)
480
                elif flush:
481
                    print("flush", do, ob1)
482
                    no_adv = 1
483
                    oaddr.next = do
484
                    obyte.next = ob1
485
                    do_flush()
486
                elif cur_cstatic - 3 > isize:
487
                    if cur_cstatic - 3 == isize + 1:
488
                        print("Put EOF", do)
489
                        cs_i = EndOfBlock
490
                        outlen = codeLength[cs_i]
491
                        outbits = code_bits[cs_i]
492
                        print("EOF BITS:", cs_i, outlen, outbits)
493
                        oaddr.next = do
494
                        obyte.next = put(outbits, outlen)
495
                        put_adv(outbits, outlen)
496
                    elif cur_cstatic - 3 == isize + 2:
497
                        print("calc end adler")
498
                        adler2.next = (adler2 + ladler1) % 65521
499
                        if doo != 0:
500
                            oaddr.next = do
501
                            obyte.next = ob1
502
                            do.next = do + 1
503
                    elif cur_cstatic - 3 == isize + 3:
504
                        print("c1")
505
                        oaddr.next = do
506
                        obyte.next = adler2 >> 8
507
                        do.next = do + 1
508
                    elif cur_cstatic - 3 == isize + 4:
509
                        print("c2")
510
                        oaddr.next = do
511
                        obyte.next = adler2 & 0xFF
512
                        do.next = do + 1
513
                    elif cur_cstatic - 3 == isize + 5:
514
                        print("c3")
515
                        oaddr.next = do
516
                        obyte.next = adler1 >> 8
517
                        do.next = do + 1
518
                    elif cur_cstatic - 3 == isize + 6:
519
                        print("c4")
520
                        oaddr.next = do
521
                        obyte.next = adler1 & 0xFF
522
                    elif cur_cstatic - 3 == isize + 7:
523
                        print("EOF finish", do)
524
                        o_done.next = True
525
                        o_oprogress.next = do + 1
526
                        state.next = d_state.IDLE
527
                    else:
528
                        print(cur_cstatic, isize)
529
                        raise Error("???")
530
                else:
531
                    bdata = iram[di]
532
                    # Fix this when > 1 byte output:
533
                    # print("cs1", bdata)
534
                    adler1_next = (adler1 + bdata) % 65521
535
                    adler1.next = adler1_next
536
                    adler2.next = (adler2 + ladler1) % 65521
537
                    ladler1.next = adler1_next
538
                    # print("in: ", bdata, di, isize)
539
                    state.next = d_state.SEARCH
540
                    cur_search.next = di - 1 # - 3
541
 
542
                if not no_adv:
543
                    cur_cstatic.next = cur_cstatic + 1
544
 
545
            elif state == d_state.DISTANCE:
546
 
547
                if flush:
548
                    do_flush()
549
                else:
550
                    # print("DISTANCE", di, do, cur_i, cur_dist)
551
                    nextdist = CopyDistance[cur_i+1]
552
                    if nextdist > cur_dist:
553
                        copydist = CopyDistance[cur_i]
554
                        # print("Found distance", copydist)
555
                        extra_dist = cur_dist - copydist
556
                        # print("extra dist", extra_dist)
557
                        extra_bits = ExtraDistanceBits[cur_i // 2]
558
                        # print("extra bits", extra_bits)
559
                        if extra_dist > ((1 << extra_bits) - 1):
560
                            raise Error("too few extra")
561
                        # print("rev", cur_i, rev_bits(cur_i, 5))
562
                        outcode = (rev_bits(cur_i, 5) | (extra_dist << 5))
563
                        # print("outcode", outcode)
564
                        oaddr.next = do
565
                        obyte.next = put(outcode, 5 + extra_bits)
566
                        put_adv(outcode, 5 + extra_bits)
567
                        #state.next = d_state.CSTATIC
568
                        cur_i.next = di - length + 1
569
                        state.next = d_state.CHECKSUM
570
                    else:
571
                        cur_i.next = cur_i + 1
572
 
573
            elif state == d_state.CHECKSUM:
574
 
575
                if cur_i < di:
576
                    # print("CHECKSUM", cur_i, di, iram[cur_i])
577
                    bdata = iram[cur_i & IBS]
578
                    adler1_next = (adler1 + bdata) % 65521
579
                    adler1.next = adler1_next
580
                    adler2.next = (adler2 + ladler1) % 65521
581
                    ladler1.next = adler1_next
582
                    cur_i.next = cur_i.next + 1
583
                else:
584
                    state.next = d_state.CSTATIC
585
 
586
            elif state == d_state.SEARCH:
587
 
588
                if not filled:
589
                    filled.next = True
590
                elif nb < 4:
591
                    pass
592
                else:
593
                    if cur_search >= 0 \
594
                             and cur_search >= di - CWINDOW \
595
                             and di < isize - 3:
596
                        if iram[cur_search & IBS] == b1 and \
597
                                iram[cur_search+1 & IBS] == b2 and \
598
                                iram[cur_search+2 & IBS] == b3:
599
                            # Length is 3 code
600
                            lencode = 257
601
                            match = 3
602
 
603
                            if di < isize - 4 and \
604
                                    iram[cur_search+3 & IBS] == b4: # iram[di + 3 & IBS]:
605
                                lencode = 258
606
                                match = 4
607
                                if di < isize - 5 and \
608
                                        iram[cur_search+4 & IBS] == iram[di + 4 & IBS]:
609
                                    lencode = 259
610
                                    match = 5
611
                            """
612
                                    if di < isize - 6 and \
613
                                            iram[cur_search+5 & IBS] == iram[di + 5 & IBS]:
614
                                        lencode = 260
615
                                        match = 6
616
                                        if di < isize - 7 and \
617
                                                iram[cur_search+6 & IBS] == iram[di + 6 & IBS]:
618
                                            lencode = 261
619
                                            match = 7
620
                                            if di < isize - 8 and \
621
                                                    iram[cur_search+7 & IBS] == iram[di + 7 & IBS]:
622
                                                lencode = 262
623
                                                match = 8
624
                                                if di < isize - 9 and \
625
                                                        iram[cur_search+8 & IBS] == iram[di + 8 & IBS]:
626
                                                    lencode = 263
627
                                                    match = 9
628
                                                    if di < isize - 10 and \
629
                                                            iram[cur_search+9 & IBS] == iram[di + 9 & IBS]:
630
                                                        lencode = 264
631
                                                        match = 10
632
                            """
633
                            print("found:", cur_search, di, isize, match)
634
                            outlen = codeLength[lencode]
635
                            outbits = code_bits[lencode]
636
                            # print("BITS:", outlen, outbits)
637
                            oaddr.next = do
638
                            obyte.next = put(outbits, outlen)
639
                            put_adv(outbits, outlen)
640
 
641
                            distance = di - cur_search
642
                            # print("distance", distance)
643
                            cur_dist.next = distance
644
                            cur_i.next = 0
645
                            # adv(match * 8)
646
                            di.next = di + match
647
                            cur_cstatic.next = cur_cstatic + match - 1
648
                            length.next = match
649
                            state.next = d_state.DISTANCE
650
                        else:
651
                            cur_search.next = cur_search - 1
652
                    else:
653
                        bdata = iram[di]
654
                        # adv(8)
655
                        di.next = di + 1
656
                        outlen = codeLength[bdata]
657
                        outbits = code_bits[bdata]
658
                        # print("CBITS:", bdata, outlen, outbits)
659
                        oaddr.next = do
660
                        obyte.next = put(outbits, outlen)
661
                        put_adv(outbits, outlen)
662
                        state.next = d_state.CSTATIC
663
 
664
            elif state == d_state.STATIC:
665
 
666
                for stat_i in range(0, 144):
667
                    codeLength[stat_i].next = 8
668
                for stat_i in range(144, 256):
669
                    codeLength[stat_i].next = 9
670
                for stat_i in range(256, 280):
671
                    codeLength[stat_i].next = 7
672
                for stat_i in range(280, 288):
673
                    codeLength[stat_i].next = 8
674
                numCodeLength.next = 288
675
                cur_HF1.next = 0
676
                state.next = d_state.HF1
677
                """
678
                if cur_static < 288:
679
                    if cur_static < 144:
680
                        codeLength[cur_static].next = 8
681
                    elif cur_static < 256:
682
                        codeLength[cur_static].next = 9
683
                    elif cur_static < 280:
684
                        codeLength[cur_static].next = 7
685
                    else:
686
                        codeLength[cur_static].next = 8
687
                    cur_static.next = cur_static + 1
688
                else:
689
                    numCodeLength.next = 288
690
                    cur_HF1.next = 0
691
                    state.next = d_state.HF1
692
                """
693
 
694
            elif state == d_state.BL:
695
 
696
                if not filled:
697
                    filled.next = True
698
                elif nb < 4:
699
                    pass
700
                elif numLiterals == 0:
701
                    numLiterals.next = 257 + get4(0, 5)
702
                    print("NL:", 257 + get4(0, 5))
703
                    numDistance.next = 1 + get4(5, 5)
704
                    print("ND:", 1 + get4(5, 5))
705
                    b_numCodeLength.next = 4 + get4(10, 4)
706
                    print("NCL:", 4 + get4(10, 4))
707
                    numCodeLength.next = 0
708
                    adv(14)
709
                else:
710
                    if numCodeLength < CodeLengths:
711
                        clo_i = CodeLengthOrder[numCodeLength]
712
                        # print("CLI: ", clo_i)
713
                        if numCodeLength < b_numCodeLength:
714
                            codeLength[clo_i].next = get4(0, 3)
715
                            adv(3)
716
                        else:
717
                            # print("SKIP")
718
                            codeLength[clo_i].next = 0
719
                        numCodeLength.next = numCodeLength + 1
720
                    else:
721
                        numCodeLength.next = CodeLengths
722
                        cur_HF1.next = 0
723
                        state.next = d_state.HF1
724
 
725
            elif state == d_state.READBL:
726
 
727
                if not filled:
728
                    filled.next = True
729
                elif nb < 4:
730
                    pass
731
                elif numCodeLength < numLiterals + numDistance:
732
                    # print(numLiterals + numDistance, numCodeLength)
733
                    n_adv = 0
734
                    if code < 16:
735
                        howOften.next = 1
736
                        lastToken.next = code
737
                    elif code == 16:
738
                        howOften.next = 3 + get4(0, 2)
739
                        n_adv = 2
740
                    elif code == 17:
741
                        howOften.next = 3 + get4(0, 3)
742
                        lastToken.next = 0
743
                        n_adv = 3
744
                    elif code == 18:
745
                        howOften.next = 11 + get4(0, 7)
746
                        lastToken.next = 0
747
                        n_adv = 7
748
                    else:
749
                        raise Error("Invalid data")
750
 
751
                    # print(numCodeLength, howOften, code, di, n_adv)
752
                    if n_adv != 0:
753
                        adv(n_adv)
754
 
755
                    state.next = d_state.REPEAT
756
                else:
757
                    print("FILL UP")
758
 
759
                    for dbl_i in range(32):
760
                        dbl = 0
761
                        if dbl_i + numLiterals < numCodeLength:
762
                            dbl = int(codeLength[dbl_i + numLiterals])
763
                        # print("dbl:", dbl)
764
                        distanceLength[dbl_i].next = dbl
765
 
766
                    # print(numCodeLength, numLiterals, MaxBitLength)
767
 
768
                    cur_i.next = numLiterals
769
                    state.next = d_state.INIT3
770
 
771
            elif state == d_state.INIT3:
772
 
773
                    if cur_i < MaxBitLength:
774
                        codeLength[cur_i].next = 0
775
                        cur_i.next = cur_i + 1
776
                    else:
777
                        numCodeLength.next = MaxBitLength
778
                        method.next = 3  # Start building bit tree
779
                        cur_HF1.next = 0
780
                        state.next = d_state.HF1
781
 
782
            elif state == d_state.DISTTREE:
783
 
784
                print("DISTTREE")
785
                for dist_i in range(32):
786
                    codeLength[dist_i].next = distanceLength[dist_i]
787
                    # print(dist_i, distanceLength[dist_i])
788
                numCodeLength.next = 32
789
                method.next = 4  # Start building dist tree
790
                # cur_i.next = 0
791
                cur_HF1.next = 0
792
                state.next = d_state.HF1
793
 
794
            elif state == d_state.REPEAT:
795
 
796
                # print("HOWOFTEN: ", numCodeLength, howOften)
797
                if howOften != 0:
798
                    codeLength[numCodeLength].next = lastToken
799
                    howOften.next = howOften - 1
800
                    numCodeLength.next = numCodeLength + 1
801
                elif numCodeLength < numLiterals + numDistance:
802
                    cur_next.next = 0
803
                    state.next = d_state.NEXT
804
                else:
805
                    state.next = d_state.READBL
806
 
807
            elif state == d_state.HF1:
808
 
809
                if cur_HF1 < len(bitLengthCount):
810
                    bitLengthCount[cur_HF1].next = 0
811
                if cur_HF1 < len(d_leaves):
812
                    d_leaves[cur_HF1].next = 0
813
                if method != 4 and cur_HF1 < len(leaves):
814
                    lwaddr.next = cur_HF1
815
                    wleaf.next = 0
816
                    # leaves[cur_HF1].next = 0
817
                limit = len(leaves)
818
                if method == 4:
819
                    limit = len(d_leaves)
820
                if cur_HF1 < limit:
821
                    cur_HF1.next = cur_HF1 + 1
822
                else:
823
                    print("DID HF1 INIT")
824
                    cur_i.next = 0
825
                    state.next = d_state.HF1INIT
826
 
827
            elif state == d_state.HF1INIT:
828
                # get frequencies of each bit length and ignore 0's
829
 
830
                # print("HF1")
831
                if cur_i < numCodeLength:
832
                    j = codeLength[cur_i]
833
                    bitLengthCount[j].next = bitLengthCount[j] + 1
834
                    # print(cur_i, j, bitLengthCount[j] + 1)
835
                    cur_i.next = cur_i + 1
836
                else:
837
                    bitLengthCount[0].next = 0
838
                    state.next = d_state.HF2
839
                    cur_i.next = 1
840
                    if method == 4:
841
                        d_maxBits.next = 0
842
                    else:
843
                        maxBits.next = 0
844
                    minBits.next = MaxCodeLength
845
 
846
            elif state == d_state.HF2:
847
                # shortest and longest codes
848
 
849
                # print("HF2")
850
                if cur_i <= MaxCodeLength:
851
                    if bitLengthCount[cur_i] != 0:
852
                        if cur_i < minBits:
853
                            minBits.next = cur_i
854
                        if method == 4:
855
                            if cur_i > d_maxBits:
856
                                d_maxBits.next = cur_i
857
                        else:
858
                            if cur_i > maxBits:
859
                                maxBits.next = cur_i
860
                    cur_i.next = cur_i + 1
861
                else:
862
                    print(minBits, maxBits)
863
                    t = InstantMaxBit
864
                    if method == 4:
865
                        if t > int(d_maxBits):
866
                            t = int(d_maxBits)
867
                        d_instantMaxBit.next = t
868
                        d_instantMask.next = (1 << t) - 1
869
                    else:
870
                        if t > int(maxBits):
871
                            t = int(maxBits)
872
                        instantMaxBit.next = t
873
                        instantMask.next = (1 << t) - 1
874
                    print((1 << t) - 1)
875
                    state.next = d_state.HF3
876
                    cur_i.next = minBits
877
                    code.next = 0
878
                    for hf2_i in range(len(nextCode)):
879
                        nextCode[hf2_i].next = 0
880
                    print("to HF3")
881
 
882
            elif state == d_state.HF3:
883
                # find bit code for first element of each bitLength group
884
 
885
                # print("HF3")
886
                amb = maxBits
887
                if method == 4:
888
                    amb = d_maxBits
889
                if cur_i <= amb:
890
                    ncode = ((code + bitLengthCount[cur_i - 1]) << 1)
891
                    code.next = ncode
892
                    nextCode[cur_i].next = ncode
893
                    # print(cur_i, ncode)
894
                    cur_i.next = cur_i + 1
895
                else:
896
                    state.next = d_state.HF4
897
                    cur_i.next = 0
898
                    spread_i.next = 0
899
                    print("to HF4")
900
 
901
            elif state == d_state.HF4_2:
902
 
903
                canonical = nextCode[bits]
904
                nextCode[bits].next = nextCode[bits] + 1
905
                if bits > MaxCodeLength:
906
                    raise Error("too many bits: %d" % bits)
907
                # print(canonical, bits)
908
                reverse.next = rev_bits(canonical, bits)
909
                # print("LEAF: ", spread_i, bits, reverse, canonical)
910
                leaf.next = makeLeaf(spread_i, bits)
911
                state.next = d_state.HF4_3
912
 
913
            elif state == d_state.HF4_3:
914
 
915
                if method == 4:
916
                    d_leaves[reverse].next = leaf # makeLeaf(spread_i, bits)
917
                    if bits <= d_instantMaxBit:
918
                        if reverse + (1 << bits) <= d_instantMask:
919
                            step.next = 1 << bits
920
                            spread.next = reverse + (1 << bits)
921
                            state.next = d_state.SPREAD
922
                        else:
923
                            spread_i.next = spread_i + 1
924
                            state.next = d_state.HF4
925
                    else:
926
                        state.next = d_state.HF4
927
                        spread_i.next = spread_i + 1
928
                else:
929
                    wleaf.next = leaf
930
                    lwaddr.next = reverse
931
                    # leaves[reverse].next = leaf # makeLeaf(spread_i, bits)
932
                    code_bits[spread_i].next = reverse
933
                    if bits <= instantMaxBit:
934
                        if reverse + (1 << bits) <= instantMask:
935
                            step.next = 1 << bits
936
                            spread.next = reverse + (1 << bits)
937
                            state.next = d_state.SPREAD
938
                        else:
939
                            spread_i.next = spread_i + 1
940
                            state.next = d_state.HF4
941
                    else:
942
                        spread_i.next = spread_i + 1
943
                        state.next = d_state.HF4
944
 
945
            elif state == d_state.HF4:
946
                # create binary codes for each literal
947
 
948
                if spread_i < numCodeLength:
949
                    bits_next = codeLength[spread_i]
950
                    if bits_next != 0:
951
                        bits.next = bits_next
952
                        state.next = d_state.HF4_2
953
                    else:
954
                        spread_i.next = spread_i + 1
955
                else:
956
                    if do_compress:
957
                        state.next = d_state.CSTATIC
958
                        cur_cstatic.next = 0
959
                    elif method == 3:
960
                        state.next = d_state.DISTTREE
961
                    elif method == 4:
962
                        print("DEFLATE m2!")
963
                        state.next = d_state.NEXT
964
                    elif method == 2:
965
                        numCodeLength.next = 0
966
                        state.next = d_state.NEXT
967
                    else:
968
                        state.next = d_state.NEXT
969
                    cur_next.next = 0
970
                    cur_i.next = 0
971
 
972
            elif state == d_state.SPREAD:
973
 
974
                if method == 4:
975
                    # print(spread, spread_i)
976
                    d_leaves[spread].next = makeLeaf(
977
                        spread_i, codeLength[spread_i])
978
                else:
979
                    lwaddr.next = spread
980
                    wleaf.next = makeLeaf(spread_i, codeLength[spread_i])
981
                    # leaves[spread].next = makeLeaf(spread_i, codeLength[spread_i])
982
                # print("SPREAD:", spread, step, instantMask)
983
                aim = instantMask
984
                if method == 4:
985
                    aim = d_instantMask
986
                if spread > aim - step:
987
                    spread_i.next = spread_i + 1
988
                    state.next = d_state.HF4
989
                else:
990
                    spread.next = spread + step
991
 
992
            elif state == d_state.NEXT:
993
 
994
                if not filled:
995
                    filled.next = True
996
                elif nb < 4:
997
                    pass
998
                elif cur_next == 0:
999
                    # print("INIT:", di, dio, instantMaxBit, maxBits)
1000
                    cto = get4(0, maxBits)
1001
                    cur_next.next = 1  # instantMaxBit
1002
                    mask = (1 << instantMaxBit) - 1
1003
                    # lraddr.next = (cto & mask)
1004
                    leaf.next = leaves[cto & mask]
1005
                    # print(cur_next, mask, leaf, maxBits)
1006
                else:
1007
                    if get_bits(leaf) < 1:
1008
                        print("< 1 bits: ")
1009
                        raise Error("< 1 bits: ")
1010
                    adv(get_bits(leaf))
1011
                    if get_code(leaf) == 0:
1012
                        print("leaf 0")
1013
                    code.next = get_code(leaf)
1014
                    # print("ADV:", di, get_bits(leaf), get_code(leaf))
1015
                    if method == 2:
1016
                        state.next = d_state.READBL
1017
                    else:
1018
                        state.next = d_state.INFLATE
1019
 
1020
            elif state == d_state.D_NEXT:
1021
 
1022
                if not filled:
1023
                    filled.next = True
1024
                elif nb < 4:
1025
                    pass
1026
                else:
1027
                    # print("D_INIT:", di, dio, d_instantMaxBit, d_maxBits)
1028
                    token = code - 257
1029
                    # print("token: ", token)
1030
                    extraLength = ExtraLengthBits[token]
1031
                    # print("extra length bits:", extraLength)
1032
                    cto = get4(extraLength, d_maxBits)
1033
                    mask = (1 << d_instantMaxBit) - 1
1034
                    leaf.next = d_leaves[cto & mask]
1035
                    state.next = d_state.D_NEXT_2
1036
 
1037
            elif state == d_state.D_NEXT_2:
1038
 
1039
                if get_bits(leaf) == 0:
1040
                    raise Error("0 bits")
1041
                token = code - 257
1042
                # print("E2:", token, leaf)
1043
                tlength = CopyLength[token]
1044
                # print("tlength:", tlength)
1045
                extraLength = ExtraLengthBits[token]
1046
                # print("extra length bits:", extraLength)
1047
                tlength += get4(0, extraLength)
1048
                # print("extra length:", tlength)
1049
                distanceCode = get_code(leaf)
1050
                # print("distance code:", distanceCode)
1051
                distance = CopyDistance[distanceCode]
1052
                # print("distance:", distance)
1053
                moreBits = ExtraDistanceBits[distanceCode >> 1]
1054
                # print("more bits:", moreBits)
1055
                # print("bits:", get_bits(leaf))
1056
                mored = get4(extraLength + get_bits(leaf), moreBits)
1057
                # print("mored:", mored)
1058
                distance += mored
1059
                # print("distance more:", distance)
1060
                adv(moreBits + extraLength + get_bits(leaf))
1061
                # print("offset:", do - distance)
1062
                # print("FAIL?: ", di, dio, do, b1, b2, b3, b4)
1063
                offset.next = do - distance
1064
                length.next = tlength
1065
                # cur_next.next = 0
1066
                cur_i.next = 0
1067 3 tomtor
                oraddr.next = do - distance
1068 2 tomtor
                state.next = d_state.COPY
1069
 
1070
            elif state == d_state.INFLATE:
1071
 
1072
                    if not filled:
1073
                        filled.next = True
1074
                    elif nb < 4:  # nb <= 2 or (nb == 3 and dio > 1):
1075
                        # print("EXTRA FETCH", nb, dio)
1076
                        pass  # fetch more bytes
1077
                    elif di > isize - 3:  # checksum is 4 bytes
1078
                        state.next = d_state.IDLE
1079
                        o_done.next = True
1080
                        print("NO EOF ", di)
1081
                        raise Error("NO EOF!")
1082
                    elif code == EndOfBlock:
1083
                        print("EOF:", di, do)
1084
                        if not final:
1085
                            state.next = d_state.HEADER
1086
                        else:
1087
                            o_done.next = True
1088
                            o_oprogress.next = do
1089
                            state.next = d_state.IDLE
1090
                    else:
1091
                        if code < EndOfBlock:
1092
                            # print("B:", code, di, do)
1093
                            oaddr.next = do
1094
                            obyte.next = code
1095
                            o_oprogress.next = do + 1
1096
                            do.next = do + 1
1097
                            cur_next.next = 0
1098
                            state.next = d_state.NEXT
1099
                            # raise Error("DF!")
1100
                        elif code == InvalidToken:
1101
                            raise Error("invalid token")
1102
                        else:
1103
                            if static:
1104
                                token = code - 257
1105
                                # print("E:", token)
1106
                                tlength = CopyLength[token]
1107
                                # print("tlength", tlength)
1108
                                extraLength = ExtraLengthBits[token]
1109
                                # print("extralengthbits", extraLength)
1110
                                tlength += get4(0, extraLength)
1111
                                # print("tlength extra", tlength)
1112
                                t = get4(extraLength, 5)
1113
                                distanceCode = rev_bits(t, 5)
1114
                                # print("dcode", distanceCode)
1115
                                distance = CopyDistance[distanceCode]
1116
                                # print("distance", distance)
1117
                                moreBits = ExtraDistanceBits[distanceCode
1118
                                                                >> 1]
1119
                                distance += get4(extraLength + 5, moreBits)
1120
                                # print("distance2", distance)
1121
                                adv(extraLength + 5 + moreBits)
1122
                                # print("adv", extraLength + 5 + moreBits)
1123
                                offset.next = do - distance
1124
                                length.next = tlength
1125
                                cur_i.next = 0
1126 3 tomtor
                                oraddr.next = do - distance
1127 2 tomtor
                                state.next = d_state.COPY
1128
                            else:
1129
                                # raise Error("TO DO")
1130
                                state.next = d_state.D_NEXT
1131
                        cur_next.next = 0
1132
 
1133
            elif state == d_state.COPY:
1134
 
1135
                if not filled:
1136
                    filled.next = True
1137
                elif nb < 4:
1138
                    pass
1139
                elif method == 0:
1140
                    if cur_i < length:
1141
                        oaddr.next = do
1142
                        obyte.next = b3
1143
                        adv(8)
1144
                        cur_i.next = cur_i + 1
1145
                        do.next = do + 1
1146
                        o_oprogress.next = do + 1
1147
                    elif not final:
1148
                        state.next = d_state.HEADER
1149
                    else:
1150
                        o_oprogress.next = do # + 1
1151
                        o_done.next = True
1152
                        state.next = d_state.IDLE
1153 4 tomtor
                elif cur_i < length + 2:
1154 2 tomtor
                    oraddr.next = offset + cur_i
1155
                    if cur_i == 1:
1156
                        copy1.next = orbyte
1157 4 tomtor
                        # print("c1", cur_i, length, offset, do, orbyte)
1158
                    if cur_i == 3:
1159
                        copy2.next = orbyte
1160 2 tomtor
                    if cur_i > 1:
1161 4 tomtor
                        # Special 1 byte offset handling:
1162 2 tomtor
                        if offset + cur_i == do + 1:
1163
                            obyte.next = copy1
1164 4 tomtor
                        elif cur_i == 3 or offset + cur_i != do:
1165
                             obyte.next = orbyte
1166
                        # Special 2 byte offset handling:
1167
                        elif cur_i > 2:
1168
                            if cur_i & 1:
1169
                                obyte.next = copy2
1170
                            else:
1171
                                obyte.next = copy1
1172
                        else:  # cur_i == 2
1173
                            obyte.next = copy1
1174 2 tomtor
                        oaddr.next = do
1175
                        o_oprogress.next = do + 1
1176
                        do.next = do + 1
1177
                    cur_i.next = cur_i + 1
1178
                else:
1179
                    cur_next.next = 0
1180
                    state.next = d_state.NEXT
1181
 
1182
            else:
1183
 
1184
                print("unknown state?!")
1185
                state.next = d_state.IDLE
1186
 
1187
    return io_logic, logic, fill_buf, oramwrite, oramread
1188
 
1189
 
1190
if __name__ == "__main__":
1191
    d = deflate(Signal(intbv()[3:]), Signal(bool(0)),
1192
                Signal(intbv()[8:]), Signal(intbv()[LBSIZE:]),
1193
                Signal(intbv()[LBSIZE:]),
1194
                Signal(intbv()[8:]), Signal(intbv()[LBSIZE:]),
1195
                Signal(bool(0)), ResetSignal(1, 0, True))
1196
    d.convert()

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.