AS6500=../asxv5pxx/asxmak/linux/exe/as6500
ASLINK=../asxv5pxx/asxmak/linux/exe/aslink
-TREE_LOADER=0x800
+LZSS_LOADER=0x800
.PHONY: all
all: \
shape5.png \
shape6.png
-star_blazer.dsk: ../util/bootable.dsk star_blazer_tree_loader.bin
+star_blazer.dsk: ../util/bootable.dsk star_blazer_lzss_loader.bin
cp ../util/bootable.dsk $@
- ${DOS33} $@ SAVE B star_blazer_tree_loader.bin "STAR BLAZER TREE LOADER"
+ ${DOS33} $@ SAVE B star_blazer_lzss_loader.bin "STAR BLAZER LZSS LOADER"
-star_blazer_tree_loader.bin: \
+star_blazer_lzss_loader.bin: \
star_blazer_hires_loader.bin \
-../loader/tree_loader.bin \
-../loader/star_blazer_tree_loader.bin
- # for DHGR we need the decompressor to use the language card for temp:
- #./tree_encode_lc.py ${TREE_LOADER} ../loader/tree_loader.bin $< $@
- ../loader/tree_encode.py ${TREE_LOADER} ../loader/tree_loader.bin $< $@
- -diff -q ../loader/star_blazer_tree_loader.bin $@
+../loader/lzss_loader.bin \
+../loader/star_blazer_lzss_loader.bin
+ ../loader/lzss_encode.py ${LZSS_LOADER} ../loader/lzss_loader.bin $< $@
+ -diff -q ../loader/star_blazer_lzss_loader.bin $@
star_blazer_hires_loader.bin: \
star_blazer.ihx \
+++ /dev/null
-#!/usr/bin/env python3
-
-# similar to ../loader/tree_encode.py, but puts the left and right
-# tables into language card, saving 0x200 bytes and allowing us to
-# load code to a maximum of 0xc000 rather than 0xbe00 as previously
-
-import bisect
-import numpy
-import sys
-from heapdict import heapdict
-
-EXIT_SUCCESS = 0
-EXIT_FAILURE = 1
-
-if len(sys.argv) < 5:
- print(f'usage: {sys.argv[0]:s} load_addr tree_loader.bin in.bin out.bin')
- sys.exit(EXIT_FAILURE)
-load_addr = int(sys.argv[1], 0)
-tree_loader_bin = sys.argv[2]
-in_bin = sys.argv[3]
-out_bin = sys.argv[4]
-
-with open(tree_loader_bin, 'rb') as fin:
- tree_loader = list(fin.read())
-assert len(tree_loader) == 0x90
-
-with open(in_bin, 'rb') as fin:
- data = list(fin.read())
- hdr = data[:4]
- bin = data[4:]
-load_addr0 = hdr[0] | (hdr[1] << 8)
-load_size0 = hdr[2] | (hdr[3] << 8)
-assert load_size0 == len(bin)
-
-# absorb a jump to the real entry point, ensuring that we
-# can losslessly reconstruct the jump when decoding later
-entry_point = load_addr0
-if bin[0] == 0x4c: # jmp NNNN
- entry_point = bin[1] | (bin[2] << 8)
- assert entry_point != load_addr0 + 3
-
- bin = bin[3:]
- load_addr0 += 3
- load_size0 -= 3
-
-freq = heapdict() #{}
-for i in range(len(bin) - 1):
- pair = tuple(bin[i:i + 2])
- if pair not in freq:
- freq[pair] = 0
- freq[pair] -= 1
-
-# define a gray code to circularly partition the token space 0x100..0x1ff
-# this makes tokens that have a left child occupy a contiguous region, and
-# tokens that have a right child a contiguous region, and they may overlap
-# we initially define the token space as 0x100..0x4ff and collapse it later
-gray_code = {
- (False, False): 0x100,
- (False, True ): 0x200,
- (True , True ): 0x300,
- (True , False): 0x400,
-}
-
-tokens = []
-for i in range(0x100):
- best, _ = freq.peekitem()
- #_, best = min([(v, k) for k, v in freq.items()])
-
- token = i | gray_code[(best[0] >= 0x100, best[1] >= 0x100)]
- tokens.append((token, best))
-
- j = 0
- while True:
- try:
- j = bin.index(best[0], j)
- except ValueError:
- break
- if j + 1 < len(bin) and bin[j + 1] == best[1]:
- if j >= 1:
- pair = (bin[j - 1], best[0])
- freq[pair] += 1
- pair = (pair[0], token)
- if pair not in freq:
- freq[pair] = 0
- freq[pair] -= 1
- freq[best] += 1
- if j + 2 < len(bin):
- pair = (best[1], bin[j + 2])
- freq[pair] += 1
- pair = (token, pair[1])
- if pair not in freq:
- freq[pair] = 0
- freq[pair] -= 1
- bin[j:j + 2] = [token]
- j += 1
- assert freq[best] == 0
- del freq[best]
-
-# collapse the token space 0x100..0x4ff to 0x100..0x1ff
-tokens = sorted(tokens)
-xlate = list(range(0x100)) + [0x200] * 0x400
-for i in range(len(tokens)):
- xlate[tokens[i][0]] = 0x100 + i
-pairs = [(xlate[left], xlate[right]) for _, (left, right) in tokens]
-tokens = [token for token, _ in tokens]
-bin = [xlate[i] for i in bin]
-
-# find the gray code transitions in the collapsed token space
-break1 = bisect.bisect_left(tokens, 0x200)
-break2 = bisect.bisect_left(tokens, 0x300)
-break3 = bisect.bisect_left(tokens, 0x400)
-
-pairs = numpy.array(pairs, numpy.uint16)
-bin = numpy.array(bin, numpy.uint16)
-
-left = (pairs[:, 0] & 0xff).astype(numpy.uint8)
-assert not numpy.any(pairs[:break2, 0] >> 8)
-assert numpy.all(pairs[break2:, 0] >> 8)
-
-right = (pairs[:, 1] & 0xff).astype(numpy.uint8)
-assert not numpy.any(pairs[:break1, 1] >> 8)
-assert numpy.all(pairs[break1:break3, 1] >> 8)
-assert not numpy.any(pairs[break3:, 1] >> 8)
-
-n = bin.shape[0]
-m = (n + 7) >> 3
-
-# make groups of 8, with padding to decode first
-bin1 = numpy.zeros((m * 8,), numpy.uint16)
-bin1[:n] = bin
-bin = bin1.reshape((m, 8))
-
-# make groups of 9, as 8 * bits 0..7 then 1 * bit 8s to decode first
-bin1 = numpy.zeros((m, 9), numpy.uint8)
-bin1[:, :-1] = bin & 0xff
-bin1[:, 8] = numpy.bitwise_or.reduce(
- (bin >> 8) << numpy.arange(8, dtype = numpy.int32)[numpy.newaxis, :],
- 1
-)
-bin = bin1.reshape((m * 9,))
-
-# bits is preloaded so we can enter loop8 partway through a group,
-# simulate decoding the padding by appending sentinel then shifting
-count = -n
-padding = count & 7
-count = (count >> 3) & 0xffff
-bits = (((bin[-1] << 1) | 1) << padding) & 0x1ff
-bin = bin[:-1 - padding]
-
-bin = list(bin)
-left = list(left)
-right = list(right)
-tree = tree_loader + bin + left + right
-load_size = 6 + len(tree) # hack for lc, was len(tree)
-print('orig', f'{load_size0:04x}', 'tree', f'{load_size:04x}')
-
-src = load_addr + load_size - 0x200
-dest = load_addr0 + load_size0
-left0 = src
-left1 = 0xd000 # hack for lc, was dest
-right0 = src + 0x100
-right1 = 0xd100 # hack for lc, was dest + 0x100
-dest -= 1
-
-assert tree[6] == 0xb9 # lda NNNN,y
-tree[7] = left0 & 0xff
-tree[8] = left0 >> 8
-assert tree[9] == 0x99 # sta NNNN,y
-tree[0xa] = left1 & 0xff
-tree[0xb] = left1 >> 8
-
-assert tree[0xc] == 0xb9 # lda NNNN,y
-tree[0xd] = right0 & 0xff
-tree[0xe] = right0 >> 8
-assert tree[0xf] == 0x99 # sta NNNN,y
-tree[0x10] = right1 & 0xff
-tree[0x11] = right1 >> 8
-
-assert tree[0x15] == 0xa9 # lda #NN
-tree[0x16] = src & 0xff
-assert tree[0x19] == 0xa9 # lda #NN
-tree[0x1a] = src >> 8
-
-assert tree[0x1d] == 0xa9 # lda #NN
-tree[0x1e] = dest & 0xff
-assert tree[0x21] == 0xa9 # lda #NN
-tree[0x22] = dest >> 8
-
-assert tree[0x25] == 0xa9 # lda #NN
-tree[0x26] = count & 0xff
-assert tree[0x29] == 0xa9 # lda #NN
-tree[0x2a] = count >> 8
-
-assert tree[0x2d] == 0xa9 # lda #NN
-tree[0x2e] = bits & 0xff
-assert tree[0x2f] == 0x18 # clc
-tree[0x2f] |= (bits >> 3) & 0x20 # clc or sec
-
-assert tree[0x5f] == 0x4c # jmp NNNN
-tree[0x60] = entry_point & 0xff
-tree[0x61] = entry_point >> 8
-
-assert tree[0x64] == 0xe9 # sbc #NN
-tree[0x65] = break3
-assert tree[0x66] == 0xc9 # cmp #NN
-tree[0x67] = (break1 - break3) & 0xff
-
-assert tree[0x68] == 0xbd # lda NNNN,x
-tree[0x69] = right1 & 0xff
-tree[0x6a] = right1 >> 8
-
-assert tree[0x79] == 0xc9 # cmp #NN
-tree[0x7a] = break2
-
-assert tree[0x7b] == 0xbd # lda NNNN,x
-tree[0x7c] = left1 & 0xff
-tree[0x7d] = left1 >> 8
-
-tree = [0xad, 0x87, 0xc0] * 2 + tree # hack for lc
-
-hdr = [load_addr & 0xff, load_addr >> 8, load_size & 0xff, load_size >> 8]
-with open(out_bin, 'wb') as fout:
- fout.write(bytes(hdr + tree))
# pip3 install --user intelhex
HEX2BIN=hex2bin.py
-RLE_LOADER=0x800
-RLE2_LOADER=0x800
-TREE_LOADER=0x800
LZSS_LOADER=0x800
HIRES_LOADER=0x2000
star_blazer.bin \
star_blazer_dejunked0.bin \
star_blazer_dejunked1.bin \
-star_blazer_lzss_loader.bin \
-star_blazer_tree_loader.bin \
-star_blazer_rle2_loader.bin \
-star_blazer_rle_loader.bin
+star_blazer_lzss_loader.bin
star_blazer.bin: ../orig/Star_Blazer_1981_Star_Craft.do
${DOS33} ../orig/Star_Blazer_1981_Star_Craft.do LOAD "STAR BLAZER" $@
lzss_loader.rel: lzss_loader.asm
${AS6500} -l -o $<
-star_blazer_tree_loader.bin: tree_loader.bin star_blazer_hires_loader.bin
- ./tree_encode.py ${TREE_LOADER} $^ $@
-
-tree_loader.bin: tree_loader.ihx
- ${HEX2BIN} $< $@
-
-tree_loader.ihx: tree_loader.rel
- ${ASLINK} -n -m -u -i -b text=${TREE_LOADER} $@ $^
-
-tree_loader.rel: tree_loader.asm
- ${AS6500} -l -o $<
-
-star_blazer_rle2_loader.bin: rle2_loader.bin star_blazer_hires_loader.bin
- ./rle2_encode.py ${RLE2_LOADER} $^ $@
-
-rle2_loader.bin: rle2_loader.ihx
- ${HEX2BIN} $< $@
-
-rle2_loader.ihx: rle2_loader.rel
- ${ASLINK} -n -m -u -i -b text=${RLE2_LOADER} $@ $^
-
-rle2_loader.rel: rle2_loader.asm
- ${AS6500} -l -o $<
-
-star_blazer_rle_loader.bin: rle_loader.bin star_blazer_hires_loader.bin
- ./rle_encode.py ${RLE_LOADER} $^ $@
-
-rle_loader.bin: rle_loader.ihx
- ${HEX2BIN} $< $@
-
-rle_loader.ihx: rle_loader.rel
- ${ASLINK} -n -m -u -i -b text=${RLE_LOADER} $@ $^
-
-rle_loader.rel: rle_loader.asm
- ${AS6500} -l -o $<
-
star_blazer_hires_loader.bin: hires_loader.bin star_blazer_dejunked0.bin
./hires_loader.py $^ $@
+++ /dev/null
-#!/usr/bin/env python3
-
-import sys
-
-EXIT_SUCCESS = 0
-EXIT_FAILURE = 1
-
-# key byte is partitioned as follows
-KEY_EOF = 0
-KEY_LIT = 1 # literal lengths 01..af
-KEY_RUN = 0xa8 # run lengths 02..49
-KEY_PAIR_RUN = 0xf0 # pair run lengths 03..12
-N_KEYS = 0x100
-
-if len(sys.argv) < 3:
- print(f'usage: {sys.argv[0]:s} in.bin out.bin')
- sys.exit(EXIT_FAILURE)
-in_bin = sys.argv[1]
-out_bin = sys.argv[2]
-
-with open(in_bin, 'rb') as fin:
- data = list(fin.read())
- hdr = data[:4]
- rle2 = data[4:]
-load_addr0 = hdr[0] | (hdr[1] << 8)
-load_size0 = hdr[2] | (hdr[3] << 8)
-assert load_size0 == len(rle2)
-
-assert rle2[0] == 0xa9 # lda #NN
-assert rle2[4] == 0xa9 # lda #NN
-src = rle2[1] | (rle2[5] << 8)
-assert src == load_addr0 + load_size0 - 1
-
-assert rle2[8] == 0xa9 # lda #NN
-assert rle2[0xc] == 0xa9 # lda #NN
-dest = rle2[9] + (rle2[0xd] << 8)
-
-assert rle2[0x6b] == 0x4c # jmp NNNN
-entry_point = rle2[0x6c] | (rle2[0x6d] << 8)
-
-rle2 = rle2[0xa1:]
-bin = []
-while True:
- count = rle2.pop()
- if count == KEY_EOF:
- break
- if count < KEY_RUN:
- bin.extend(rle2[-1:-count - 1:-1])
- del rle2[-count:]
- elif count < KEY_PAIR_RUN:
- count -= KEY_RUN - 2
- bin.extend(rle2[-1:] * count)
- del rle2[-1:]
- else:
- count -= KEY_PAIR_RUN - 3
- bin.extend(rle2[-1:-3:-1] * (count >> 1) + rle2[-1:] * (count & 1))
- del rle2[-2:]
-assert len(rle2) == 0
-bin = bin[::-1]
-
-load_size = len(bin)
-print(f'rle2 {load_size0:04x} orig {load_size:04x}')
-
-load_addr = dest + 1 - load_size
-if entry_point != load_addr:
- bin = [0x4c, entry_point & 0xff, entry_point >> 8] + bin # jmp NNNN
- load_addr -= 3
- load_size += 3
-
-hdr = [load_addr & 0xff, load_addr >> 8, load_size & 0xff, load_size >> 8]
-with open(out_bin, 'wb') as fout:
- fout.write(bytes(hdr + bin))
+++ /dev/null
-#!/usr/bin/env python3
-
-import sys
-
-EXIT_SUCCESS = 0
-EXIT_FAILURE = 1
-
-# key byte is partitioned as follows
-KEY_EOF = 0
-KEY_LIT = 1 # literal lengths 01..a7
-KEY_RUN = 0xa8 # run lengths 02..49
-KEY_PAIR_RUN = 0xf0 # pair run lengths 03..12
-N_KEYS = 0x100
-
-MAX_LIT = KEY_RUN - KEY_LIT # a7
-MAX_RUN = KEY_PAIR_RUN - KEY_RUN + 1 # 49
-MAX_PAIR_RUN = N_KEYS - KEY_PAIR_RUN + 2 # 12
-
-if len(sys.argv) < 5:
- print(f'usage: {sys.argv[0]:s} load_addr rle2_loader.bin in.bin out.bin')
- sys.exit(EXIT_FAILURE)
-load_addr = int(sys.argv[1], 0)
-rle2_loader_bin = sys.argv[2]
-in_bin = sys.argv[3]
-out_bin = sys.argv[4]
-
-with open(rle2_loader_bin, 'rb') as fin:
- rle2_loader = list(fin.read())
-assert len(rle2_loader) == 0xa1
-
-with open(in_bin, 'rb') as fin:
- data = list(fin.read())
- hdr = data[:4]
- bin = data[4:]
-load_addr0 = hdr[0] | (hdr[1] << 8)
-load_size0 = hdr[2] | (hdr[3] << 8)
-assert load_size0 == len(bin)
-
-# absorb a jump to the real entry point, ensuring that we
-# can losslessly reconstruct the jump when decoding later
-entry_point = load_addr0
-if bin[0] == 0x4c: # jmp NNNN
- entry_point = bin[1] | (bin[2] << 8)
- assert entry_point != load_addr0 + 3
-
- bin = bin[3:]
- load_addr0 += 3
- load_size0 -= 3
-
-rle2 = []
-while len(bin):
- # look for a run
- count = 1
- while (
- count < MAX_RUN and
- len(bin) >= count + 1 and
- bin[-count - 1] == bin[-1]
- ):
- count += 1
-
- # since we are in key mode we can output runs of at least 2
- if count >= 2:
- rle2.extend([KEY_RUN + count - 2, bin[-1]])
- del bin[-count:]
- else:
- # look for a run of pairs
- count = 2
- while (
- count < MAX_PAIR_RUN and
- len(bin) >= count + 1 and
- bin[-count - 1] == bin[-(count & 1) - 1]
- ):
- count += 1
-
- # since we are in key mode we can output pair runs of at least 3
- if count >= 3:
- rle2.extend([KEY_PAIR_RUN + count - 3] + bin[-1:-3:-1])
- del bin[-count:]
- else:
- # we will have to start literal mode
- # stop with a run of a least 3 or pair run of at least 4
- count = 1
- while (
- count < MAX_LIT and
- count < len(bin) and
- (
- len(bin) < count + 3 or
- bin[-count - 2] != bin[-count - 1] or
- bin[-count - 3] != bin[-count - 1]
- )
- and
- (
- len(bin) < count + 4 or
- bin[-count - 3] != bin[-count - 1] or
- bin[-count - 4] != bin[-count - 2]
- )
- ):
- count += 1
-
- # but do not stop in the middle of a pair
- if (
- count == MAX_LIT and
- len(bin) >= count + 1 and
- bin[-count - 1] == bin[-count]
- ):
- count -= 1
-
- rle2.extend([KEY_LIT + count - 1] + bin[-1:-count - 1:-1])
- del bin[-count:]
-rle2.append(KEY_EOF)
-
-rle2 = rle2_loader + rle2[::-1]
-load_size = len(rle2)
-
-print(f'orig {load_size0:04x} rle2 {load_size:04x}')
-
-src = load_addr + load_size - 1
-dest = load_addr0 + load_size0 - 1
-
-assert rle2[0] == 0xa9 # lda #NN
-rle2[1] = src & 0xff
-assert rle2[4] == 0xa9 # lda #NN
-rle2[5] = src >> 8
-
-assert rle2[8] == 0xa9 # lda #NN
-rle2[9] = dest & 0xff
-assert rle2[0xc] == 0xa9 # lda #NN
-rle2[0xd] = dest >> 8
-
-assert rle2[0x6b] == 0x4c # jmp NNNN
-rle2[0x6c] = entry_point & 0xff
-rle2[0x6d] = entry_point >> 8
-
-hdr = [load_addr & 0xff, load_addr >> 8, load_size & 0xff, load_size >> 8]
-with open(out_bin, 'wb') as fout:
- fout.write(bytes(hdr + rle2))
+++ /dev/null
-; key byte is partitioned as follows
-KEY_EOF = 0
-KEY_LIT = 1 ; literal lengths 01..a7
-KEY_RUN = 0xa8 ; run lengths 02..49
-KEY_PAIR_RUN = 0xf0 ; pair run lengths 03..12
-N_KEYS = 0x100
-
- .r65c02
-
- .area zpage
- .setdp
-
- .ds 80
-src: .ds 2 ; address of next byte to read
-dest: .ds 2 ; address of next byte to write
-count: .ds 1 ; scratch for calculating decrement
-swap: .ds 1 ; value to xor onto data each byte
-
- .area text
-
- lda #0
- sta src
- lda #0
- sta src + 1
-
- lda #0
- sta dest
- lda #0
- sta dest + 1
-
- ldy #0
-loop: lda [src],y
- beq done
- cmp #KEY_RUN
- bcs run
-
- ; lit
- sta count
- tay
-
- ; src -= count + 1
- ;clc
- lda src
- sbc count
- sta src
- lda src + 1
- sbc #0
- sta src + 1
-
- ; dest -= count
- ;sec
- lda dest
- sbc count
- sta dest
- lda dest + 1
- sbc #0
- sta dest + 1
-
-0$: lda [src],y
- sta [dest],y
- dey
- bne 0$
- beq loop
-
-run: cmp #KEY_PAIR_RUN
- bcs pair_run
-
- sec
- sbc #KEY_RUN - 2
- sta count
-
- ; src -= 2
- ;sec
- lda src
- sbc #2
- sta src
- lda src + 1
- sbc #0
- sta src + 1
-
- ; dest -= count
- ;sec
- lda dest
- sbc count
- sta dest
- lda dest + 1
- sbc #0
- sta dest + 1
-
- iny
- lda [src],y
-
- ldy count
-0$: sta [dest],y
- dey
- bne 0$
- beq loop
-
-done: jmp 0
-
-pair_run:
- sec
- sbc #KEY_PAIR_RUN - 3
- sta count
-
- ; src -= 3
- ;sec
- lda src
- sbc #3
- sta src
- lda src + 1
- sbc #0
- sta src + 1
-
- ; dest -= count
- ;sec
- lda dest
- sbc count
- sta dest
- lda dest + 1
- sbc #0
- sta dest + 1
-
- iny
- lda [src],y
- iny
- eor [src],y
- sta swap
- lda [src],y
-
- ldy count
-0$: sta [dest],y
- eor swap
- dey
- bne 0$
- jmp loop
+++ /dev/null
-#!/usr/bin/env python3
-
-import sys
-
-EXIT_SUCCESS = 0
-EXIT_FAILURE = 1
-
-# key byte is partitioned as follows
-KEY_EOF = 0
-KEY_LIT = 1 # literal lengths 01..af
-KEY_RUN = 0xb0 # run lengths 02..51
-N_KEYS = 0x100
-
-if len(sys.argv) < 3:
- print(f'usage: {sys.argv[0]:s} in.bin out.bin')
- sys.exit(EXIT_FAILURE)
-in_bin = sys.argv[1]
-out_bin = sys.argv[2]
-
-with open(in_bin, 'rb') as fin:
- data = list(fin.read())
- hdr = data[:4]
- rle = data[4:]
-load_addr0 = hdr[0] | (hdr[1] << 8)
-load_size0 = hdr[2] | (hdr[3] << 8)
-assert load_size0 == len(rle)
-
-assert rle[0] == 0xa9 # lda #NN
-assert rle[4] == 0xa9 # lda #NN
-src = rle[1] | (rle[5] << 8)
-assert src == load_addr0 + load_size0 - 1
-
-assert rle[8] == 0xa9 # lda #NN
-assert rle[0xc] == 0xa9 # lda #NN
-dest = rle[9] + (rle[0xd] << 8)
-
-assert rle[0x67] == 0x4c # jmp NNNN
-entry_point = rle[0x68] | (rle[0x69] << 8)
-
-rle = rle[0x6a:]
-bin = []
-while True:
- count = rle.pop()
- if count == KEY_EOF:
- break
- if count < KEY_RUN:
- bin.extend(rle[-1:-count - 1:-1])
- del rle[-count:]
- else:
- count -= KEY_RUN - 2
- bin.extend(rle[-1:] * count)
- del rle[-1:]
-assert len(rle) == 0
-bin = bin[::-1]
-
-load_size = len(bin)
-print(f'rle {load_size0:04x} orig {load_size:04x}')
-
-load_addr = dest + 1 - load_size
-if entry_point != load_addr:
- bin = [0x4c, entry_point & 0xff, entry_point >> 8] + bin # jmp NNNN
- load_addr -= 3
- load_size += 3
-
-hdr = [load_addr & 0xff, load_addr >> 8, load_size & 0xff, load_size >> 8]
-with open(out_bin, 'wb') as fout:
- fout.write(bytes(hdr + bin))
+++ /dev/null
-#!/usr/bin/env python3
-
-import sys
-
-EXIT_SUCCESS = 0
-EXIT_FAILURE = 1
-
-# key byte is partitioned as follows
-KEY_EOF = 0
-KEY_LIT = 1 # literal lengths 01..af
-KEY_RUN = 0xb0 # run lengths 02..51
-N_KEYS = 0x100
-
-MAX_LIT = KEY_RUN - KEY_LIT # af
-MAX_RUN = N_KEYS - KEY_RUN + 1 # 51
-
-if len(sys.argv) < 5:
- print(f'usage: {sys.argv[0]:s} load_addr rle_loader.bin in.bin out.bin')
- sys.exit(EXIT_FAILURE)
-load_addr = int(sys.argv[1], 0)
-rle_loader_bin = sys.argv[2]
-in_bin = sys.argv[3]
-out_bin = sys.argv[4]
-
-with open(rle_loader_bin, 'rb') as fin:
- rle_loader = list(fin.read())
-assert len(rle_loader) == 0x6a
-
-with open(in_bin, 'rb') as fin:
- data = list(fin.read())
- hdr = data[:4]
- bin = data[4:]
-load_addr0 = hdr[0] | (hdr[1] << 8)
-load_size0 = hdr[2] | (hdr[3] << 8)
-assert load_size0 == len(bin)
-
-# absorb a jump to the real entry point, ensuring that we
-# can losslessly reconstruct the jump when decoding later
-entry_point = load_addr0
-if bin[0] == 0x4c: # jmp NNNN
- entry_point = bin[1] | (bin[2] << 8)
- assert entry_point != load_addr0 + 3
-
- bin = bin[3:]
- load_addr0 += 3
- load_size0 -= 3
-
-rle = []
-while len(bin):
- # look for a run
- count = 1
- while (
- count < MAX_RUN and
- len(bin) >= count + 1 and
- bin[-count - 1] == bin[-1]
- ):
- count += 1
-
- # since we are in key mode we can output runs of at least 2
- if count >= 2:
- rle.extend([KEY_RUN + count - 2, bin[-1]])
- del bin[-count:]
- else:
- # we will have to start literal mode, stop with a run of at least 3
- count = 1
- while (
- count < MAX_LIT and count < len(bin) and (
- len(bin) < count + 3 or
- bin[-count - 2] != bin[-count - 1] or
- bin[-count - 3] != bin[-count - 1]
- )
- ):
- count += 1
-
- # but do not stop in the middle of a pair
- if (
- count == MAX_LIT and
- len(bin) >= count + 1 and
- bin[-count - 1] == bin[-count]
- ):
- count -= 1
-
- rle.extend([KEY_LIT + count - 1] + bin[-1:-count - 1:-1])
- del bin[-count:]
-rle.append(KEY_EOF)
-
-rle = rle_loader + rle[::-1]
-load_size = len(rle)
-
-print(f'orig {load_size0:04x} rle {load_size:04x}')
-
-src = load_addr + load_size - 1
-dest = load_addr0 + load_size0 - 1
-
-assert rle[0] == 0xa9 # lda #NN
-rle[1] = src & 0xff
-assert rle[4] == 0xa9 # lda #NN
-rle[5] = src >> 8
-
-assert rle[8] == 0xa9 # lda #NN
-rle[9] = dest & 0xff
-assert rle[0xc] == 0xa9 # lda #NN
-rle[0xd] = dest >> 8
-
-assert rle[0x67] == 0x4c # jmp NNNN
-rle[0x68] = entry_point & 0xff
-rle[0x69] = entry_point >> 8
-
-hdr = [load_addr & 0xff, load_addr >> 8, load_size & 0xff, load_size >> 8]
-with open(out_bin, 'wb') as fout:
- fout.write(bytes(hdr + rle))
+++ /dev/null
-; key byte is partitioned as follows
-KEY_EOF = 0
-KEY_LIT = 1 ; literal lengths 01..af
-KEY_RUN = 0xb0 ; run lengths 02..51
-N_KEYS = 0x100
-
- .r65c02
-
- .area zpage
- .setdp
-
- .ds 80
-src: .ds 2 ; address of next byte to read
-dest: .ds 2 ; address of next byte to write
-count: .ds 1
-
- .area text
-
- lda #0
- sta src
- lda #0
- sta src + 1
-
- lda #0
- sta dest
- lda #0
- sta dest + 1
-
- ldy #0
-loop: lda [src],y
- beq done
- cmp #KEY_RUN
- bcs run
-
- ; lit
- sta count
- tay
-
- ; src -= count + 1
- ;clc
- lda src
- sbc count
- sta src
- lda src + 1
- sbc #0
- sta src + 1
-
- ; dest -= count
- ;sec
- lda dest
- sbc count
- sta dest
- lda dest + 1
- sbc #0
- sta dest + 1
-
-0$: lda [src],y
- sta [dest],y
- dey
- bne 0$
- beq loop
-
-run: sec
- sbc #KEY_RUN - 2
- sta count
-
- ; src -= 2
- ;sec
- lda src
- sbc #2
- sta src
- lda src + 1
- sbc #0
- sta src + 1
-
- ; dest -= count
- ;sec
- lda dest
- sbc count
- sta dest
- lda dest + 1
- sbc #0
- sta dest + 1
-
- iny
- lda [src],y
-
- ldy count
-0$: sta [dest],y
- dey
- bne 0$
- beq loop
-
-done: jmp 0
+++ /dev/null
-#!/usr/bin/env python3
-
-import sys
-
-EXIT_SUCCESS = 0
-EXIT_FAILURE = 1
-
-if len(sys.argv) < 3:
- print(f'usage: {sys.argv[0]:s} in.bin out.bin')
- sys.exit(EXIT_FAILURE)
-in_bin = sys.argv[1]
-out_bin = sys.argv[2]
-
-with open(in_bin, 'rb') as fin:
- data = list(fin.read())
- hdr = data[:4]
- tree = data[4:]
-load_addr0 = hdr[0] | (hdr[1] << 8)
-load_size0 = hdr[2] | (hdr[3] << 8)
-assert load_size0 == len(tree)
-
-assert tree[0x15] == 0xa9 # lda #NN
-assert tree[0x19] == 0xa9 # lda #NN
-src = tree[0x16] | (tree[0x1a] << 8)
-
-assert tree[0x1d] == 0xa9 # lda #NN
-assert tree[0x21] == 0xa9 # lda #NN
-dest = tree[0x1e] + (tree[0x22] << 8)
-
-assert tree[0x25] == 0xa9 # lda #NN
-assert tree[0x29] == 0xa9 # lda #NN
-count = tree[0x26] + (tree[0x2a] << 8)
-
-assert tree[0x2d] == 0xa9 # lda #NN
-assert tree[0x2f] & ~0x20 == 0x18 # clc
-bits = tree[0x2e] | ((tree[0x2f] & 0x20) << 3)
-
-assert tree[0x5f] == 0x4c # jmp NNNN
-entry_point = tree[0x60] | (tree[0x61] << 8)
-
-assert tree[0x64] == 0xe9 # sbc #NN
-break3 = tree[0x65]
-assert tree[0x66] == 0xc9 # cmp #NN
-break1 = (tree[0x67] + break3) & 0xff
-
-assert tree[0x79] == 0xc9 # cmp #NN
-break2 = tree[0x7a]
-
-assert src == load_addr0 + load_size0 - 0x200
-left = tree[-0x200:-0x100]
-right = tree[-0x100:]
-tree = [0] + tree[0x90:-0x200] # 0 is sentinel for last dummy bits load
-
-bin = []
-def decode(_bytes, bits):
- while bits & 0xff:
- byte = _bytes.pop()
- if bits & 0x100:
- decode(
- [left[byte], right[byte]],
- (
- 0x40
- if byte < break1 else
- 0x140
- if byte < break2 else
- 0x1c0
- if byte < break3 else
- 0xc0
- )
- )
- else:
- bin.append(byte)
- bits <<= 1
- assert len(_bytes) == 0
-
-padding = 0
-while (bits & (1 << padding)) == 0:
- padding += 1
-n = 8 - padding
-
-count |= (-1 << 16)
-while count < 0:
- decode(tree[-n:], bits)
- del tree[-n:]
-
- bits = (tree.pop() << 1) | 1
- n = 8
-
- count += 1
-assert len(tree) == 0
-bin = bin[::-1]
-
-load_size = len(bin)
-print(f'tree {load_size0:04x} orig {load_size:04x}')
-
-load_addr = dest + 1 - load_size
-if entry_point != load_addr:
- bin = [0x4c, entry_point & 0xff, entry_point >> 8] + bin # jmp NNNN
- load_addr -= 3
- load_size += 3
-
-hdr = [load_addr & 0xff, load_addr >> 8, load_size & 0xff, load_size >> 8]
-with open(out_bin, 'wb') as fout:
- fout.write(bytes(hdr + bin))
+++ /dev/null
-#!/usr/bin/env python3
-
-import bisect
-import numpy
-import sys
-from heapdict import heapdict
-
-EXIT_SUCCESS = 0
-EXIT_FAILURE = 1
-
-if len(sys.argv) < 5:
- print(f'usage: {sys.argv[0]:s} load_addr tree_loader.bin in.bin out.bin')
- sys.exit(EXIT_FAILURE)
-load_addr = int(sys.argv[1], 0)
-tree_loader_bin = sys.argv[2]
-in_bin = sys.argv[3]
-out_bin = sys.argv[4]
-
-with open(tree_loader_bin, 'rb') as fin:
- tree_loader = list(fin.read())
-assert len(tree_loader) == 0x90
-
-with open(in_bin, 'rb') as fin:
- data = list(fin.read())
- hdr = data[:4]
- bin = data[4:]
-load_addr0 = hdr[0] | (hdr[1] << 8)
-load_size0 = hdr[2] | (hdr[3] << 8)
-assert load_size0 == len(bin)
-
-# absorb a jump to the real entry point, ensuring that we
-# can losslessly reconstruct the jump when decoding later
-entry_point = load_addr0
-if bin[0] == 0x4c: # jmp NNNN
- entry_point = bin[1] | (bin[2] << 8)
- assert entry_point != load_addr0 + 3
-
- bin = bin[3:]
- load_addr0 += 3
- load_size0 -= 3
-
-freq = heapdict() #{}
-for i in range(len(bin) - 1):
- pair = tuple(bin[i:i + 2])
- if pair not in freq:
- freq[pair] = 0
- freq[pair] -= 1
-
-# define a gray code to circularly partition the token space 0x100..0x1ff
-# this makes tokens that have a left child occupy a contiguous region, and
-# tokens that have a right child a contiguous region, and they may overlap
-# we initially define the token space as 0x100..0x4ff and collapse it later
-gray_code = {
- (False, False): 0x100,
- (False, True ): 0x200,
- (True , True ): 0x300,
- (True , False): 0x400,
-}
-
-tokens = []
-for i in range(0x100):
- best, _ = freq.peekitem()
- #_, best = min([(v, k) for k, v in freq.items()])
-
- token = i | gray_code[(best[0] >= 0x100, best[1] >= 0x100)]
- tokens.append((token, best))
-
- j = 0
- while True:
- try:
- j = bin.index(best[0], j)
- except ValueError:
- break
- if j + 1 < len(bin) and bin[j + 1] == best[1]:
- if j >= 1:
- pair = (bin[j - 1], best[0])
- freq[pair] += 1
- pair = (pair[0], token)
- if pair not in freq:
- freq[pair] = 0
- freq[pair] -= 1
- freq[best] += 1
- if j + 2 < len(bin):
- pair = (best[1], bin[j + 2])
- freq[pair] += 1
- pair = (token, pair[1])
- if pair not in freq:
- freq[pair] = 0
- freq[pair] -= 1
- bin[j:j + 2] = [token]
- j += 1
- assert freq[best] == 0
- del freq[best]
-
-# collapse the token space 0x100..0x4ff to 0x100..0x1ff
-tokens = sorted(tokens)
-xlate = list(range(0x100)) + [0x200] * 0x400
-for i in range(len(tokens)):
- xlate[tokens[i][0]] = 0x100 + i
-pairs = [(xlate[left], xlate[right]) for _, (left, right) in tokens]
-tokens = [token for token, _ in tokens]
-bin = [xlate[i] for i in bin]
-
-# find the gray code transitions in the collapsed token space
-break1 = bisect.bisect_left(tokens, 0x200)
-break2 = bisect.bisect_left(tokens, 0x300)
-break3 = bisect.bisect_left(tokens, 0x400)
-
-pairs = numpy.array(pairs, numpy.uint16)
-bin = numpy.array(bin, numpy.uint16)
-
-left = (pairs[:, 0] & 0xff).astype(numpy.uint8)
-assert not numpy.any(pairs[:break2, 0] >> 8)
-assert numpy.all(pairs[break2:, 0] >> 8)
-
-right = (pairs[:, 1] & 0xff).astype(numpy.uint8)
-assert not numpy.any(pairs[:break1, 1] >> 8)
-assert numpy.all(pairs[break1:break3, 1] >> 8)
-assert not numpy.any(pairs[break3:, 1] >> 8)
-
-n = bin.shape[0]
-m = (n + 7) >> 3
-
-# make groups of 8, with padding to decode first
-bin1 = numpy.zeros((m * 8,), numpy.uint16)
-bin1[:n] = bin
-bin = bin1.reshape((m, 8))
-
-# make groups of 9, as 8 * bits 0..7 then 1 * bit 8s to decode first
-bin1 = numpy.zeros((m, 9), numpy.uint8)
-bin1[:, :-1] = bin & 0xff
-bin1[:, 8] = numpy.bitwise_or.reduce(
- (bin >> 8) << numpy.arange(8, dtype = numpy.int32)[numpy.newaxis, :],
- 1
-)
-bin = bin1.reshape((m * 9,))
-
-# bits is preloaded so we can enter loop8 partway through a group,
-# simulate decoding the padding by appending sentinel then shifting
-count = -n
-padding = count & 7
-count = (count >> 3) & 0xffff
-bits = (((bin[-1] << 1) | 1) << padding) & 0x1ff
-bin = bin[:-1 - padding]
-
-bin = list(bin)
-left = list(left)
-right = list(right)
-tree = tree_loader + bin + left + right
-load_size = len(tree)
-print('orig', f'{load_size0:04x}', 'tree', f'{load_size:04x}')
-
-src = load_addr + load_size - 0x200
-dest = load_addr0 + load_size0
-left0 = src
-left1 = dest
-right0 = src + 0x100
-right1 = dest + 0x100
-dest -= 1
-
-assert tree[6] == 0xb9 # lda NNNN,y
-tree[7] = left0 & 0xff
-tree[8] = left0 >> 8
-assert tree[9] == 0x99 # sta NNNN,y
-tree[0xa] = left1 & 0xff
-tree[0xb] = left1 >> 8
-
-assert tree[0xc] == 0xb9 # lda NNNN,y
-tree[0xd] = right0 & 0xff
-tree[0xe] = right0 >> 8
-assert tree[0xf] == 0x99 # sta NNNN,y
-tree[0x10] = right1 & 0xff
-tree[0x11] = right1 >> 8
-
-assert tree[0x15] == 0xa9 # lda #NN
-tree[0x16] = src & 0xff
-assert tree[0x19] == 0xa9 # lda #NN
-tree[0x1a] = src >> 8
-
-assert tree[0x1d] == 0xa9 # lda #NN
-tree[0x1e] = dest & 0xff
-assert tree[0x21] == 0xa9 # lda #NN
-tree[0x22] = dest >> 8
-
-assert tree[0x25] == 0xa9 # lda #NN
-tree[0x26] = count & 0xff
-assert tree[0x29] == 0xa9 # lda #NN
-tree[0x2a] = count >> 8
-
-assert tree[0x2d] == 0xa9 # lda #NN
-tree[0x2e] = bits & 0xff
-assert tree[0x2f] == 0x18 # clc
-tree[0x2f] |= (bits >> 3) & 0x20 # clc or sec
-
-assert tree[0x5f] == 0x4c # jmp NNNN
-tree[0x60] = entry_point & 0xff
-tree[0x61] = entry_point >> 8
-
-assert tree[0x64] == 0xe9 # sbc #NN
-tree[0x65] = break3
-assert tree[0x66] == 0xc9 # cmp #NN
-tree[0x67] = (break1 - break3) & 0xff
-
-assert tree[0x68] == 0xbd # lda NNNN,x
-tree[0x69] = right1 & 0xff
-tree[0x6a] = right1 >> 8
-
-assert tree[0x79] == 0xc9 # cmp #NN
-tree[0x7a] = break2
-
-assert tree[0x7b] == 0xbd # lda NNNN,x
-tree[0x7c] = left1 & 0xff
-tree[0x7d] = left1 >> 8
-
-hdr = [load_addr & 0xff, load_addr >> 8, load_size & 0xff, load_size >> 8]
-with open(out_bin, 'wb') as fout:
- fout.write(bytes(hdr + tree))
+++ /dev/null
- .r65c02
-
-FASTER = 1
-
- .area zpage
- .setdp
-
- .ds 0x80
-src: .ds 2 ; address of last byte read
-dest: .ds 2 ; address of next byte to write
-count: .ds 2 ; negative count of 8-token groups
-bits: .ds 1 ; buffers bit 8 of tokens in group
-
- .area text
-
- cld
- ldx #0xff
- txs
-
- ldy #0
-0$: lda 0,y ; left0 (above encoded data)
- sta 0,y ; left1 (above decoded data)
- lda 0,y ; right0 (above encoded data)
- sta 0,y ; right1 (above decoded data)
- iny
- bne 0$
-
- lda #0
- sta src
- lda #0
- sta src + 1
-
- lda #0
- sta dest
- lda #0
- sta dest + 1
-
- lda #0
- sta count
- lda #0
- sta count + 1
-
- lda #0
- clc
-loop8: sta bits
-
-loop1: lda src
- bne 0$
- dec src + 1
-0$: dec src
-
- lda [src],y
-.if FASTER
- bcs token
- sta [dest],y
-
- lda dest
- bne 1$
- dec dest + 1
-1$: dec dest
-.else ; smaller
- jmp expand
-.endif
-
-expand_ret0:
- ;clc
- rol bits
- bne loop1
-
- lda src
- bne 1$
- dec src + 1
-1$: dec src
-
- lda [src],y
- ;sec
- rol a
-
- inc count
- bne loop8
- inc count + 1
- bne loop8
-
- jmp 0
-
-token: ; enter with 9-bit byte in cf:a (and we know cf=1, it is token)
- pha
- tax
-
- sbc #0 ; break3
- cmp #0 ; (break1 - break3) & 0xff
-
- ; asxxxx inconsistency:
- ; lda 0,x seems to default to lda *0,x whereas lda 0,y does not
- lda 0xaaaa,x ; right1 (above decoded data)
-.if FASTER
- bcs token
- sta [dest],y
-
- lda dest
- bne 0$
- dec dest + 1
-0$: dec dest
-.else ; smaller
- jmp expand
-.endif
-
-expand_ret1:
- pla
- tax
-
- cmp #0 ; break2
-
- lda 0xaaaa,x ; left1 (above decoded data)
-expand: ; enter with 9-bit byte in cf:a
- bcs token
- sta [dest],y
-
- lda dest
- bne 0$
- dec dest + 1
-0$: dec dest
-
- tsx
- inx
- beq expand_ret0 ; we need cf=0 here
- bne expand_ret1 ; we need cf=0 here