--- /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) == 0x91
+
+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[0x60] == 0x4c # jmp NNNN
+tree[0x61] = entry_point & 0xff
+tree[0x62] = entry_point >> 8
+
+assert tree[0x65] == 0xe9 # sbc #NN
+tree[0x66] = break3
+assert tree[0x67] == 0xc9 # cmp #NN
+tree[0x68] = (break1 - break3) & 0xff
+
+assert tree[0x69] == 0xbd # lda NNNN,x
+tree[0x6a] = right1 & 0xff
+tree[0x6b] = right1 >> 8
+
+assert tree[0x7a] == 0xc9 # cmp #NN
+tree[0x7b] = break2
+
+assert tree[0x7c] == 0xbd # lda NNNN,x
+tree[0x7d] = left1 & 0xff
+tree[0x7e] = 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))
public / star_disasm.git / commitdiff