Optimistic compression approach

kimstik commented 4 months ago

The following code of write_bitstream() will hang on data that has less than three unused values:

        lst = bitmatrix.histogram(bs, bins=[i for i in range(257)]) # 257 iso that the last basket is [255, 256] and not [254, 255]
        [key8Z, key4Z, key2Z] = [i for i,val in enumerate(lst) if val==0][0:3]

yrabbit commented 4 months ago

Can you suggest a fix? It's just not my area at all.

trabucayre commented 4 months ago

Indeed, this code may produce error/crash if less than 3 keys are found. Have you a design with this situation occur? Is it possible to you share it? I'm interested to see how gowin deal with this use case (no compression or compression with 1 or 2 keys instead of 3). Quick fix may be to check the size and disable compression when len < 3.

kimstik commented 4 months ago

I have a situation where gowin IDE ignores "set_option -bit_compress 1" When I try to compress it via bslib.py it crashes because no keys are found.

from bslib import read_bitstream, write_bitstream
bs, hdr, ftr = read_bitstream(sys.argv[1])
write_bitstream(sys.argv[2], bs, hdr, ftr, compress=True)

you may expose statistics by following code

lst, _ = np.histogram(bs, bins=[i for i in range(256)])
print(np.sort(lst))

Result for 2 different bitstreams:

[      0       0       0       0       0       0       0       0       0
       0       0       0       0       0       0       0       0       0
       0       0       0       0       0       0       0       0       0
       0       0       0       0       0       0       0       0       0
       0       0       0       0       0       0       0       0       0
       0       0       0       0       0       0       0       0       0
       0       0       0       0       0       0       0       0       0
       0       0       0       0       0       0       0       0       0
       1       1       1       1       1       1       1       1       1
       1       1       1       1       1       1       1       1       1
       1       1       1       1       1       1       1       1       1
       1       1       1       1       1       1       1       1       1
       1       1       1       1       1       1       1       1       1
       1       1       2       2       2       2       2       2       2
       2       2       2       2       2       2       2       2       2
       2       2       2       2       2       2       2       2       2
       2       2       2       2       2       2       2       3       3
       3       3       3       3       3       3       3       3       3
       3       3       3       3       3       4       4       4       4
       4       4       4       4       4       5       5       5       5
       5       5       5       5       5       5       5       5       5
       5       6       6       6       6       7       7       7       8
       9       9       9      10      10      10      10      10      10
      11      11      12      13      13      13      13      14      14
      14      16      16      17      18      18      20      20      21
      24      26      27      29      30      32      39      48      50
      51      52      55      56      61      68      68      72      74
      76      86     187     240     266     284     305     348     391
     420    8174 1406130]

[     28      30      35      37      38      38      38      41      42
      43      43      44      45      46      49      49      49      50
      50      53      53      54      55      57      58      59      59
      59      60      62      62      63      64      66      68      69
      71      71      71      72      75      75      76      77      78
      80      80      80      81      82      82      83      83      84
      87      88      91      91      94      94      95      96      99
     101     104     104     105     105     106     106     107     108
     108     115     116     116     122     123     124     127     131
     131     133     134     136     140     141     142     142     144
     146     146     151     152     153     155     156     157     157
     158     160     161     162     165     166     167     168     169
     171     172     176     179     179     179     181     184     185
     186     188     189     190     194     195     195     198     199
     200     201     201     202     203     204     208     209     209
     212     213     213     213     213     214     214     217     218
     220     224     227     229     231     233     234     234     236
     238     252     253     258     259     265     268     269     269
     272     272     285     287     289     291     293     293     294
     295     303     304     305     305     305     307     314     331
     335     336     348     351     356     359     372     375     378
     414     414     427     435     441     458     480     492     535
     543     552     552     593     611     643     708     714     716
     718     730     760     762     837     885     888     929     945
     986    1033    1040    1091    1098    1142    1177    1205    1250
    1264    1290    1316    1319    1354    1512    1573    1613    1755
    1778    1876    2019    2500    2522    2602    2636    3099    3163
    3345    3537    8031    8278    9969    9998   11288   12026   12344
   12442   15639 2109806]

Last one have no chance to be compressed

perhaps it may be solved by following?

def write_bitstream(fname, bs, hdr, ftr, compress):
    if 256-len(np.unique(bs)) < 3: compress = False

or without numpy if you wish:

def write_bitstream(fname, bs, hdr, ftr, compress):
    if 256-len(set(bs)) < 3: compress = False

YosysHQ / apicula

Optimistic compression approach #235