ii-vision/transcoder/screen.py

1008 lines
36 KiB
Python
Raw Permalink Normal View History

"""Various representations of Apple II video display."""
import bz2
import functools
import pickle
from typing import Union, List, Optional, Tuple
import numpy as np
import palette as pal
2019-06-14 21:03:37 +00:00
# Type annotation for cases where we may process either an int or a numpy array.
IntOrArray = Union[np.uint64, np.ndarray]
2019-06-14 21:03:37 +00:00
def y_to_base_addr(y: int, page: int = 0) -> int:
"""Maps y coordinate to base address on given screen page."""
a = y // 64
d = y - 64 * a
b = d // 8
c = d - 8 * b
addr = 8192 * (page + 1) + 1024 * c + 128 * b + 40 * a
return addr
Y_TO_BASE_ADDR = [
[y_to_base_addr(y, screen_page) for y in range(192)]
for screen_page in (0, 1)
]
# Array mapping (page, offset) to x (byte) and y coords respectively
# TODO: is np.dtype(int) faster for these?
PAGE_OFFSET_TO_X = np.zeros((32, 256), dtype=np.uint8)
PAGE_OFFSET_TO_Y = np.zeros((32, 256), dtype=np.uint8)
# Inverse mappings
X_Y_TO_PAGE = np.zeros((192, 40), dtype=np.uint8)
X_Y_TO_OFFSET = np.zeros((192, 40), dtype=np.uint8)
# Mask of which (page, offset) bytes represent screen holes
2023-01-17 12:26:25 +00:00
SCREEN_HOLES = np.full((32, 256), True, dtype=np.bool8)
# Dict mapping memory address to (page, y, x_byte) tuple
ADDR_TO_COORDS = {}
def _populate_mappings():
for y in range(192):
for x in range(40):
y_base = Y_TO_BASE_ADDR[0][y]
page = y_base >> 8
offset = y_base - (page << 8) + x
PAGE_OFFSET_TO_Y[page - 32, offset] = y
PAGE_OFFSET_TO_X[page - 32, offset] = x
X_Y_TO_PAGE[y, x] = page - 32
X_Y_TO_OFFSET[y, x] = offset
# This (page, offset) is not a screen hole
SCREEN_HOLES[page - 32, offset] = False
for p in range(2):
a = Y_TO_BASE_ADDR[p][y] + x
ADDR_TO_COORDS[a] = (p, y, x)
_populate_mappings()
class FlatMemoryMap:
"""Linear 8K representation of HGR screen memory."""
2019-03-21 16:04:26 +00:00
def __init__(self, screen_page: int, data: np.array = None):
if screen_page not in [1, 2]:
raise ValueError("Screen page out of bounds: %d" % screen_page)
self.screen_page = screen_page # type: int
self._addr_start = 8192 * self.screen_page
self._addr_end = self._addr_start + 8191
self.data = None # type: np.array
if data is not None:
if data.shape != (8192,):
raise ValueError("Unexpected shape: %r" % (data.shape,))
self.data = data
else:
self.data = np.zeros((8192,), dtype=np.uint8)
def to_memory_map(self):
return MemoryMap(self.screen_page, self.data.reshape((32, 256)))
def write(self, addr: int, val: int) -> None:
"""Updates screen image to set 0xaddr = val (including screen holes)"""
if addr < self._addr_start or addr > self._addr_end:
raise ValueError("Address out of range: 0x%04x" % addr)
self.data[addr - self._addr_start] = val
class MemoryMap:
"""Page/offset-structured representation of HGR screen memory."""
2019-03-21 16:04:26 +00:00
def __init__(self, screen_page: int, page_offset: np.array = None):
if screen_page not in [1, 2]:
raise ValueError("Screen page out of bounds: %d" % screen_page)
self.screen_page = screen_page # type: int
self._page_start = 32 * screen_page
self.page_offset = None # type: np.array
if page_offset is not None:
if page_offset.shape != (32, 256):
raise ValueError("Unexpected shape: %r" % (page_offset.shape,))
self.page_offset = page_offset
else:
self.page_offset = np.zeros((32, 256), dtype=np.uint8)
def to_flat_memory_map(self) -> FlatMemoryMap:
return FlatMemoryMap(self.screen_page, self.page_offset.reshape(8192))
def write(self, page: int, offset: int, val: int) -> None:
"""Updates screen image to set (page, offset)=val (inc. screen holes)"""
self.page_offset[page - self._page_start][offset] = val
class Bitmap:
"""Packed bitmap representation of (D)HGR screen memory.
Maintains a page-based array whose entries contain a packed representation
of multiple screen bytes, in a representation that supports efficiently
determining the visual effect of storing bytes at arbitrary screen offsets.
"""
# NOTE: See https://github.com/numpy/numpy/issues/2524 and related issues
# for why we have to cast things explicitly to np.uint64 - type promotion
# to uint64 is broken in numpy :(
# Name of bitmap type
NAME = None # type: str
# Size of packed representation, consisting of header + body + footer
HEADER_BITS = None # type: np.uint64
BODY_BITS = None # type: np.uint64
FOOTER_BITS = None # type: np.uint64
# How many bits of packed representation are necessary to determine the
# effect of storing a memory byte, e.g. because they influence pixel
# colour or are influenced by other bits.
MASKED_BITS = None # type: np.uint64
# How many coloured screen pixels we can extract from MASKED_BITS. Note
# that this does not include the last 3 dots represented by the footer,
# since we don't have enough information to determine their colour (we
# would fall off the end of the 4-bit sliding window)
MASKED_DOTS = None # type: np.uint64
# List of bitmasks for extracting the subset of packed data corresponding
# to bits influencing/influenced by a given byte offset. These must be
# a contiguous bit mask, i.e. so that after shifting they are enumerated
# by 0..2**MASKED_BITS-1
BYTE_MASKS = None # type: List[np.uint64]
BYTE_SHIFTS = None # type: List[np.uint64]
# NTSC clock phase at first masked bit
PHASES = None # type: List[int]
def __init__(
self,
palette: pal.Palette,
main_memory: MemoryMap,
aux_memory: Optional[MemoryMap]
):
self.palette = palette # type: pal.Palette
self.main_memory = main_memory # type: MemoryMap
self.aux_memory = aux_memory # type: Optional[MemoryMap]
self.PACKED_BITS = (
self.HEADER_BITS + self.BODY_BITS + self.FOOTER_BITS
) # type: np.uint64
# How many screen bytes we pack into a single scalar
self.SCREEN_BYTES = np.uint64(len(self.BYTE_MASKS)) # type: np.uint64
self.packed = np.empty(
shape=(32, 128), dtype=np.uint64) # type: np.ndarray
self._pack()
# TODO: don't leak headers/footers across screen rows. We should be using
# x-y representation rather than page-offset
@staticmethod
def _make_header(col: IntOrArray) -> IntOrArray:
"""Extract values to use as header of next column."""
raise NotImplementedError
def _body(self) -> np.ndarray:
"""Pack related screen bytes into an efficient representation."""
raise NotImplementedError
@staticmethod
def _make_footer(col: IntOrArray) -> IntOrArray:
"""Extract values to use as footer of previous column."""
raise NotImplementedError
def _pack(self) -> None:
"""Pack MemoryMap into efficient representation for diffing."""
body = self._body()
# Prepend last 3 bits of previous odd byte so we can correctly
# decode the effective colours at the beginning of the 22-bit tuple
prev_col = np.roll(body, 1, axis=1).astype(np.uint64)
header = self._make_header(prev_col)
# Don't leak header across page boundaries
header[:, 0] = 0
# Append first 3 bits of next even byte so we can correctly
# decode the effective colours at the end of the 22-bit tuple
next_col = np.roll(body, -1, axis=1).astype(np.uint64)
footer = self._make_footer(next_col)
# Don't leak footer across page boundaries
footer[:, -1] = 0
self.packed = header ^ body ^ footer
@staticmethod
def masked_update(
byte_offset: int,
old_value: IntOrArray,
new_value: np.uint8) -> IntOrArray:
"""Update int/array to store new value at byte_offset in every entry.
Does not patch up headers/footers of neighbouring columns.
"""
raise NotImplementedError
@staticmethod
@functools.lru_cache(None)
def byte_offset(page_offset: int, is_aux: bool) -> int:
"""Map screen offset for aux/main into offset within packed data."""
raise NotImplementedError
@staticmethod
@functools.lru_cache(None)
def _byte_offsets(is_aux: bool) -> Tuple[int, int]:
"""Return byte offsets within packed data for AUX/MAIN memory."""
raise NotImplementedError
@classmethod
def to_dots(cls, masked_val: int, byte_offset: int) -> int:
"""Convert masked representation to bit sequence of display dots."""
raise NotImplementedError
def apply(
self,
page: int,
offset: int,
is_aux: bool,
value: np.uint8) -> None:
"""Update packed representation of changing main/aux memory."""
byte_offset = self.byte_offset(offset, is_aux)
packed_offset = offset // 2
self.packed[page, packed_offset] = self.masked_update(
byte_offset, self.packed[page, packed_offset], value)
self._fix_scalar_neighbours(page, packed_offset, byte_offset)
if is_aux:
self.aux_memory.write(page, offset, value)
else:
self.main_memory.write(page, offset, value)
def _fix_scalar_neighbours(
self,
page: int,
offset: int,
byte_offset: int) -> None:
"""Fix up column headers/footers when updating a (page, offset)."""
if byte_offset == 0 and offset > 0:
self.packed[page, offset - 1] = self._fix_column_left(
self.packed[page, offset - 1],
self.packed[page, offset]
)
elif byte_offset == (self.SCREEN_BYTES - 1) and offset < 127:
# Need to also update the 3-bit header of the next column
self.packed[page, offset + 1] = self._fix_column_right(
self.packed[page, offset + 1],
self.packed[page, offset]
)
def _fix_column_left(
self,
column_left: IntOrArray,
column: IntOrArray
) -> IntOrArray:
"""Patch up the footer of the column to the left."""
# Mask out footer(s)
column_left &= np.uint64(2 ** (self.HEADER_BITS + self.BODY_BITS) - 1)
column_left ^= self._make_footer(column)
return column_left
def _fix_column_right(
self,
column_right: IntOrArray,
column: IntOrArray
) -> IntOrArray:
"""Patch up the header of the column to the right."""
# Mask out header(s)
column_right &= np.uint64(
(2 ** (self.BODY_BITS + self.FOOTER_BITS) - 1)) << self.HEADER_BITS
column_right ^= self._make_header(column)
return column_right
def _fix_array_neighbours(
self,
ary: np.ndarray,
byte_offset: int
) -> None:
"""Fix up column headers/footers for all array entries."""
# TODO: don't leak header/footer across page boundaries
# Propagate new value into neighbouring byte headers/footers if
# necessary
if byte_offset == 0:
# Need to also update the footer of the preceding column
shifted_left = np.roll(ary, -1, axis=1)
self._fix_column_left(ary, shifted_left)
elif byte_offset == (self.SCREEN_BYTES - 1):
# Need to also update the header of the next column
shifted_right = np.roll(ary, 1, axis=1)
self._fix_column_right(ary, shifted_right)
@classmethod
@functools.lru_cache(None)
def edit_distances(cls, palette_id: pal.Palette) -> np.ndarray:
"""Load edit distance matrices for masked, shifted byte values."""
data = "transcoder/data/%s_palette_%d_edit_distance.npz" % (
cls.NAME, palette_id.value
)
dist = np.load(data)['edit_distance']
# dist is an upper-triangular matrix of edit_distance(a, b)
# encoded as dist[(a << N) + b] = edit_distance(a, b)
# Because the distance metric is reflexive,
# edit_distance(b, a) = edit_distance(a, b)
identity = np.arange(2 ** (2 * cls.MASKED_BITS), dtype=np.uint64)
# Swap values of form a << N + b to b << N + a
transpose = (identity >> cls.MASKED_BITS) + (
(identity & np.uint64(2 ** cls.MASKED_BITS - 1)) <<
cls.MASKED_BITS)
for i in range(dist.shape[0]):
dist[i, transpose] += dist[i, identity]
return dist
@classmethod
def mask_and_shift_data(
cls,
data: IntOrArray,
byte_offset: int) -> IntOrArray:
"""Masks and shifts packed data into the MASKED_BITS range."""
res = (data & cls.BYTE_MASKS[byte_offset]) >> (
cls.BYTE_SHIFTS[byte_offset])
assert np.all(res <= 2 ** cls.MASKED_BITS)
return res
# Can't cache all possible values but this seems to give a good enough hit
# rate without costing too much memory
# TODO: unit tests
@functools.lru_cache(10 ** 6)
def byte_pair_difference(
self,
byte_offset: int,
old_packed: np.uint64,
content: np.uint8
) -> np.uint16:
"""Compute effect of storing a new content byte within packed data."""
old_pixels = self.mask_and_shift_data(old_packed, byte_offset)
new_pixels = self.mask_and_shift_data(
self.masked_update(byte_offset, old_packed, content), byte_offset)
pair = (old_pixels << self.MASKED_BITS) + new_pixels
return self.edit_distances(self.palette)[byte_offset][pair]
def diff_weights(
self,
source: "Bitmap",
is_aux: bool
) -> np.ndarray:
"""Compute edit distance matrix from source bitmap."""
return self._diff_weights(source.packed, is_aux)
# TODO: unit test
def _diff_weights(
self,
source_packed: np.ndarray,
is_aux: bool,
content: np.uint8 = None
) -> np.ndarray:
"""Computes edit distance matrix from source_packed to self.packed
If content is set, the distance will be computed as if this value
was stored into each offset position of source_packed, i.e. to
allow evaluating which offsets (if any) should be chosen for storing
this content byte.
"""
2023-01-17 12:26:25 +00:00
diff = np.ndarray((32, 256), dtype=np.int32)
offsets = self._byte_offsets(is_aux)
dists = []
for o in offsets:
if content is not None:
compare_packed = self.masked_update(o, source_packed, content)
self._fix_array_neighbours(compare_packed, o)
else:
compare_packed = source_packed
# Pixels influenced by byte offset o
source_pixels = self.mask_and_shift_data(compare_packed, o)
target_pixels = self.mask_and_shift_data(self.packed, o)
# Concatenate N-bit source and target into 2N-bit values
pair = (source_pixels << self.MASKED_BITS) + target_pixels
dist = self.edit_distances(self.palette)[o][pair].reshape(
pair.shape)
dists.append(dist)
# Interleave even/odd columns
diff[:, 0::2] = dists[0]
diff[:, 1::2] = dists[1]
return diff
# TODO: combine with _diff_weights
# TODO: unit test
def _diff_weights_page(
self,
source_packed: np.ndarray,
target_packed: np.ndarray,
is_aux: bool,
content: np.uint8 = None
) -> np.ndarray:
"""Computes edit distance matrix from source_packed to self.packed
If content is set, the distance will be computed as if this value
was stored into each offset position of source_packed, i.e. to
allow evaluating which offsets (if any) should be chosen for storing
this content byte.
"""
diff = np.ndarray((256,), dtype=np.int32)
offsets = self._byte_offsets(is_aux)
dists = []
for o in offsets:
if content is not None:
compare_packed = self.masked_update(o, source_packed, content)
self._fix_array_neighbours(compare_packed, o)
else:
compare_packed = source_packed
# Pixels influenced by byte offset o
source_pixels = self.mask_and_shift_data(compare_packed, o)
target_pixels = self.mask_and_shift_data(target_packed, o)
# Concatenate N-bit source and target into 2N-bit values
pair = (source_pixels << self.MASKED_BITS) + target_pixels
dist = self.edit_distances(self.palette)[o][pair].reshape(
pair.shape)
dists.append(dist)
# Interleave even/odd columns
diff[0::2] = dists[0]
diff[1::2] = dists[1]
return diff
def _check_consistency(self):
"""Sanity check that headers and footers are consistent."""
headers = np.roll(self._make_header(self.packed), 1, axis=1).astype(
np.uint64)
footers = np.roll(self._make_footer(self.packed), -1, axis=1).astype(
np.uint64)
mask_hf = np.uint64(0b1110000000000000000000000000000111)
res = (self.packed ^ headers ^ footers) & mask_hf
nz = np.transpose(np.nonzero(res))
ok = True
if nz.size != 0:
for p, o in nz.tolist():
if o == 0 or o == 127:
continue
ok = False
print(p, o, bin(self.packed[p, o - 1]),
bin(headers[p, o]),
bin(self.packed[p, o]),
bin(self.packed[p, o + 1]), bin(footers[p, o]),
bin(res[p, o])
)
assert ok
# TODO: unit tests
def compute_delta_page(
self,
page: int,
content: int,
diff_weights: np.ndarray,
is_aux: bool
) -> np.ndarray:
"""Compute which content stores introduce the least additional error.
We compute the effect of storing content at all possible offsets
within self.packed, and then subtract the previous diff weights.
Negative values indicate that the new content value is closer to the
target than the current content.
"""
# TODO: use error edit distance?
packed_page = self.packed[page, :].reshape(1, -1)
new_diff = self._diff_weights_page(
packed_page, packed_page, is_aux, content)
return new_diff - diff_weights
class HGRBitmap(Bitmap):
"""Packed bitmap representation of HGR screen memory.
The HGR display is encoded in a somewhat complicated way, so we have to
do a bit of work to turn it into a useful format.
Each screen byte consists of a palette bit (7) and 6 data bits (0..6)
Each non-palette bit turns on two consecutive display dots, with bit 6
repeated a third time. This third dot may or may not be overwritten by the
effect of the next byte.
Turning on the palette bit shifts that byte's dots right by one
position.
Given two neighbouring screen bytes Aaaaaaaa, Bbbbbbbb (at even and odd
offsets), where capital letter indicates the position of the palette bit,
we use the following 22-bit packed representation:
2211111111110000000000 <-- bit position in uint22
1098765432109876543210
ffFbbbbbbbBAaaaaaaaHhh
h and f are headers/footers derived from the neighbouring screen bytes.
Since our colour artifact model (see colours.py) uses a sliding 4-bit window
onto the dot string, we need to also include a 3-bit header and footer
to account for the influence from/on neighbouring bytes, i.e. adjacent
packed values. These are just the low/high 2 data bits of the 16-bit
body of those neighbouring columns, plus the corresponding palette bit.
This 22-bit packed representation is sufficient to compute the effects
(on pixel colours) of storing a byte at even or odd offsets. From it we
can extract the bit stream of displayed HGR dots, and the mapping to pixel
colours follows the HGRColours bitmap, see colours.py.
We put the two A/B palette bits next to each other so that we can
mask a contiguous range of bits whose colours influence/are influenced by
storing a byte at a given offset.
We need to mask out bit subsequences of size 3+8+3=14, i.e. the 8-bits
corresponding to the byte being stored, plus the neighbouring 3 bits that
influence it/are influenced by it.
Note that the masked representation has the same size for both offsets (
14 bits), but different meaning, since the palette bit is in a different
position.
With this masked representation, we can precompute an edit distance for the
pixel changes resulting from all possible HGR byte stores, see
make_edit_distance.py.
The edit distance matrix is encoded by concatenating the 14-bit source
and target masked values into a 28-bit pair, which indexes into the
edit_distance array to give the corresponding edit distance.
"""
NAME = 'HGR'
# Size of packed representation, consisting of header + body + footer
HEADER_BITS = np.uint64(3)
# 2x 8-bit screen bytes
BODY_BITS = np.uint64(16)
FOOTER_BITS = np.uint64(3)