SHARE
TWEET

zcomp

Zeda Jan 22nd, 2020 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. saveSScreen       = 86ECh
  2. zcomp_vars        = 8478h
  3. zcomp_freq_table  = saveSScreen
  4. zcomp_keymap      = 8700h
  5. zcomp_input_base  = zcomp_vars
  6. zcomp_input_size  = zcomp_vars+2
  7. zcomp_partition_len=zcomp_input_size+2
  8. zcomp_table_len   = zcomp_partition_len+2
  9. zcomp_best_size   = zcomp_table_len+2
  10. zcomp_part0_size  = zcomp_best_size+3
  11. zcomp_part1_size  = zcomp_part0_size+2
  12.  
  13. zcomp:
  14.   ld (zcomp_input_base),hl
  15.   ld (zcomp_input_size),bc
  16.   push de
  17.  
  18. ;initialize the frequency table
  19.   ld hl,zcomp_freq_table
  20.   ld bc,0
  21. _:
  22.   ld (hl),c
  23.   inc hl
  24.   ld (hl),c
  25.   inc hl
  26.   ld (hl),b
  27.   inc hl
  28.   inc b
  29.   jr nz,-_
  30.  
  31. ;Now count the frequencies
  32.   ld hl,(zcomp_input_base)
  33.   ld bc,(zcomp_input_size)
  34. zcomp_freq_loop:
  35.   push hl
  36.   push bc
  37.   ld b,0
  38.   ld c,(hl)
  39.   ld hl,zcomp_freq_table
  40.   add hl,bc
  41.   add hl,bc
  42.   add hl,bc
  43.   inc (hl)
  44.   jr nz,$+4
  45.   inc hl
  46.   inc (hl)
  47.   pop bc
  48.   pop hl
  49.   cpi
  50.   jp pe,zcomp_freq_loop
  51.  
  52. ;Now sort by frequency
  53.   ld ix,zcomp_sort
  54.   ld bc,256
  55.   call heapsort
  56.  
  57. ;Count the number of unique bytes
  58.   ld c,0
  59.   ld hl,zcomp_freq_table+766
  60. _:
  61.   ld a,(hl)
  62.   dec hl
  63.   or (hl)
  64.   jr z,+_
  65.   dec hl
  66.   dec hl
  67.   inc c
  68.   jr nz,-_
  69. _:
  70.   ld a,c
  71.   ld (zcomp_table_len),a
  72.  
  73. ;count the size of the first partition
  74.   ld hl,(zcomp_freq_table+765)
  75.   ld (zcomp_part0_size),hl
  76.   ex de,hl
  77.   ld hl,(zcomp_input_size)
  78.   ;or a
  79.   sbc hl,de
  80.   ld (zcomp_part1_size),hl
  81.  
  82. ;Set up the partitions
  83.   ld hl,-1
  84.   ld (zcomp_best_size),hl
  85.   ld (zcomp_best_size+1),hl
  86.   ld a,1
  87.   ld (zcomp_partition_len),a
  88.   ld hl,zcomp_freq_table+765
  89.   push hl
  90. partition_loop:
  91.   call zcomp_getsize
  92.   ld a,(zcomp_partition_len)
  93.   ld b,a
  94.   add a,a
  95.   ld (zcomp_partition_len),a
  96.   ld hl,(zcomp_best_size)
  97.   ld a,(zcomp_best_size+2)
  98.   ;or a
  99.   sbc hl,de
  100.   sbc a,c
  101.   jr c,zcomp_partition_found
  102.   or h
  103.   or l
  104.   jr z,zcomp_partition_found
  105.  
  106.   ld a,c
  107.   ld (zcomp_best_size),de
  108.   ld (zcomp_best_size+2),a
  109.   ex (sp),hl
  110.   push bc
  111. _:
  112.   push bc
  113.   dec hl
  114.   dec hl
  115.   ld b,(hl)
  116.   dec hl
  117.   ld c,(hl)
  118.   push hl
  119.  
  120.   ld hl,(zcomp_part0_size)
  121.   add hl,bc
  122.   ld (zcomp_part0_size),hl
  123.  
  124.   ld hl,(zcomp_part1_size)
  125.   ;or a
  126.   sbc hl,bc
  127.   ld (zcomp_part1_size),hl
  128.  
  129.   pop hl
  130.   pop bc
  131.   djnz -_
  132.   pop af
  133.   ex (sp),hl
  134.   ;check if 2a<zcomp_table_len
  135.   add a,a
  136.   jr c,zcomp_partition_found
  137.   ld hl,zcomp_table_len
  138.   sub (hl)
  139.   jr c,partition_loop
  140.  
  141. zcomp_partition_found:
  142.   pop hl
  143.   pop hl
  144.  
  145. ;Now we write the key to the output
  146. ;first is the size of the key
  147.   ld a,(zcomp_table_len)
  148.   ld b,a
  149.   ld (hl),a
  150.   inc hl
  151.  
  152. ;next is the size of the first partition
  153.   ld a,(zcomp_partition_len)
  154.   rrca
  155.   ld (hl),a
  156.   push hl
  157.   inc hl
  158.  
  159. ;Now we write the actual key
  160.   ld de,zcomp_freq_table+767
  161. _:
  162.   ld a,(de)
  163.   ld (hl),a
  164.   inc hl
  165.   dec de
  166.   dec de
  167.   dec de
  168.   djnz -_
  169.  
  170. ;Before we continue, let's make an LUT to map each byte to its code
  171.   pop hl
  172.   ld a,(hl)
  173.   inc hl
  174.   push af
  175.   ld b,a
  176.   ld c,0
  177.   dec a
  178.   jr z,+_
  179.   inc c
  180.   srl a
  181.   jr nz,$-3
  182. _:
  183.   sla c
  184.   ld d,zcomp_keymap>>8
  185. zcomp_keymap_loop_0:
  186.   ld e,(hl)
  187.   inc hl
  188.   ex de,hl
  189.   ld (hl),c
  190.   inc h
  191.   ld (hl),a
  192.   dec h
  193.   ex de,hl
  194.   inc a
  195.   djnz zcomp_keymap_loop_0
  196.  
  197.   pop bc    ;B is the size of the first partition
  198.   ld a,(zcomp_table_len)
  199.   sub b
  200.   ld b,a
  201.   ld c,0
  202.   dec a
  203.   jr z,+_
  204.   inc c
  205.   srl a
  206.   jr nz,$-3
  207. _:
  208.   sla c
  209.   inc c
  210. zcomp_keymap_loop_1:
  211.   ld e,(hl)
  212.   inc hl
  213.   ex de,hl
  214.   ld (hl),c
  215.   inc h
  216.   ld (hl),a
  217.   dec h
  218.   ex de,hl
  219.   inc a
  220.   djnz zcomp_keymap_loop_1
  221.  
  222. ;Write the size of the uncompressed data
  223.   ld bc,(zcomp_input_size)
  224.   ld (hl),c
  225.   inc hl
  226.   ld (hl),b
  227.   inc hl
  228.  
  229. ;Now start compressing and writing out the data
  230.   ld de,(zcomp_input_base)
  231.   ld (hl),1
  232. zcomp_output_loop:
  233.   ld a,(de)
  234.   inc de
  235.   push de
  236.   push bc
  237.   ld d,zcomp_keymap>>8
  238.   ld e,a
  239.   ld a,(de)
  240.   srl a
  241.   rl (hl)
  242.   jr nc,+_
  243.   inc hl
  244.   ld (hl),1
  245. _:
  246. ;A is the number of bits in the code
  247.   or a
  248.   jr z,zcomp_output_loop_end
  249.   inc d
  250.   ld b,a
  251.   ld a,8
  252.   sub b
  253.   ld c,a
  254.   ld a,(de)
  255.   jr z,+_
  256.   add a,a
  257.   dec c
  258.   jr nz,$-2
  259. _:
  260.  
  261.   add a,a
  262.   rl (hl)
  263.   jr nc,$+5
  264.   inc hl
  265.   ld (hl),1
  266.   djnz -_
  267.  
  268. zcomp_output_loop_end:
  269.   pop bc
  270.   pop de
  271.   dec bc
  272.   ld a,b
  273.   or c
  274.   jr nz,zcomp_output_loop
  275. _:
  276.   sla (hl)
  277.   jr nc,-_
  278.   inc hl
  279.   ex de,hl
  280.   ret
  281.  
  282. zcomp_getsize:
  283. ;zcomp_part0_size*log2(zcomp_partition_len);+zcomp_part1_size*log2(zcomp_table_len-zcomp_partition_len)
  284.   ld a,(zcomp_partition_len)
  285.   ld b,a
  286.   ld c,a
  287.   xor a
  288.   ld h,a
  289.   ld l,a
  290.   ld de,(zcomp_part0_size)
  291. _:
  292.   add hl,de
  293.   adc a,0
  294.   srl b
  295.   jr nz,-_
  296.  
  297.   ld b,a
  298.   inc b
  299.   ld a,(zcomp_table_len)
  300.   sub c
  301.   ld c,a
  302.   ld a,b
  303.   ld de,(zcomp_part1_size)
  304. _:
  305.   add hl,de
  306.   adc a,0
  307.   srl c
  308.   jr nz,-_
  309.   add hl,de
  310.   adc a,c
  311.   ex de,hl
  312.   ld c,a
  313.   ret
  314.  
  315. zcomp_sort:
  316.   rla
  317.   ex de,hl
  318.   ld hl,zcomp_freq_table
  319.   add hl,de
  320.   add hl,de
  321.   add hl,de
  322.   ;HL points to the first element
  323.   ex de,hl
  324.   ld hl,zcomp_freq_table
  325.   add hl,bc
  326.   add hl,bc
  327.   add hl,bc
  328.   rra
  329.   jr c,zcomp_sort_swap
  330. zcomp_sort_cmp:
  331.   ;compare the element at DE to the element at HL
  332.   inc hl
  333.   inc de
  334.   ld a,(de)
  335.   cp (hl)
  336.   ret nz
  337.   dec hl
  338.   dec de
  339.   ld a,(de)
  340.   cp (hl)
  341.   ret
  342.  
  343. zcomp_sort_swap:
  344. ;swap the 3 bytes at HL with the 3 bytes at DE
  345.   ld a,(de)
  346.   ldi
  347.   dec hl
  348.   ld (hl),a
  349.   inc hl
  350.  
  351.   ld a,(de)
  352.   ldi
  353.   dec hl
  354.   ld (hl),a
  355.   inc hl
  356.  
  357.   ld a,(de)
  358.   ldi
  359.   dec hl
  360.   ld (hl),a
  361.   ret
  362.  
  363. call_ix:
  364.   jp (ix)
  365.  
  366. #include "heapsort.z80"
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top