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

Subversion Repositories hdl-deflate

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

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

powered by: WebSVN 2.1.0

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