To see how deep this rabbit hole can get I decided to go absolutely "pure" and "self contained". If no standard library, no built-ins and no C calls allowed - what's possible?
The immediate challenge - there is no math whatsoever – no addition, multiplication, etc – and no back doors left to use those operation via C. Let's invent math ourselves!
As the Byte type is an enumeration of 256 constants (to be memory compatible with the outside world) and because it is not convenient to do math operations on that type right away (would result into giant switch statements) I made a separate Bit type:
enum Bit { case o, i }
along with the basic & | ^ ~ operations defined on it, e.g. this is bit and:
if case .i = a, case .i = b { return .i }
return .o
Then defined:
init(bits: (Bit, Bit, Bit, Bit, Bit, Bit, Bit, Bit)
var bits: (Bit, Bit, Bit, Bit, Bit, Bit, Bit, Bit)
on Byte, to go from byte to bits and vice versa.
From there is a short walk to bit operations defined on Byte type, including bit shifts:
func bsl_byte(_ a: Byte, _ b: Byte) -> Byte {
let v = a.bits
switch b {
case .x00: return a
case .x01: return .init(bits: (.o, v.0, v.1, v.2, v.3, v.4, v.5, v.6))
case .x02: return .init(bits: (.o, .o, v.0, v.1, v.2, v.3, v.4, v.5))
case .x03: return .init(bits: (.o, .o, .o, v.0, v.1, v.2, v.3, v.4))
case .x04: return .init(bits: (.o, .o, .o, .o, v.0, v.1, v.2, v.3))
case .x05: return .init(bits: (.o, .o, .o, .o, .o, v.0, v.1, v.2))
case .x06: return .init(bits: (.o, .o, .o, .o, .o, .o, v.0, v.1))
case .x07: return .init(bits: (.o, .o, .o, .o, .o, .o, .o, v.0))
case .x08: return .init(bits: (.o, .o, .o, .o, .o, .o, .o, .o))
default: return .init(bits: (.o, .o, .o, .o, .o, .o, .o, .o))
}
}
Byte addition comes next:
func add_byte(_ a: Byte, _ b: Byte) -> (result: Byte, overflow: Byte) {
var carry = band_byte(a, b)
var result = bxor_byte(a, b)
var overflow: Byte = .x00
while case .true = carry != .x00 {
overflow = bor_byte(overflow, bsr_byte(carry, .x07))
let shiftedcarry = bsl_byte(carry, .x01)
carry = band_byte(result, shiftedcarry)
result = bxor_byte(result, shiftedcarry)
}
return (result, overflow)
}
Followed by implementation of addition on a 64 bit integer type (which is just a tuple of 8 bytes in my implementation) – a simple matter of doing byte by byte addition carrying the overflow bit along and accounting for it in the next byte.
Then multiplication and division
func mul_generic<T: SupportsGenericMultiplication>(_ a: T, _ b: T) -> T {
var n = a
var x = b
let O = T()
let I = T.one
var y = O
if case .true = x.isEq(O) { return O }
if case .true = x.isEq(I) { return n }
while case .true = !n.isEq(O) {
if case .true = n.band(I).isEq(O) {
x = x.bsl(I)
n = n.bsr(I)
} else {
y = y.add(x)
x = x.bsl(I)
n = n.sub(I).bsr(I)
}
}
return y
}
func div_generic<T: SupportsGenericDivision>(_ a: T, _ b: T) -> T {
var num = a
let div = b
var ans = T()
let I = T.one
if case .true = b.isEq(I) { return a }
while case .true = div.less(num) {
var temp = div
var mul = I
while case .true = temp.bsl(I).less(num) {
mul = mul.bsl(I)
temp = temp.bsl(I)
}
ans = ans.add(mul)
num = num.sub(temp)
}
return ans
}
In the implementation I'm deliberately using explicit names like "band_byte" instead of a nicer "&" - explicit name makes it much easier refactoring the code and know which operation depends upon which and harder to get into a trap of implementing, say, addition using a loop (that in turn needs addition to operate).
This gave me a more or less complete system with basic math operations defined (in addition to lots of fun). Granted the implementation is not fast, and the resulting asm must look totally bonkers (where you'd normally see just one "add" or "mul" CPU instruction – you'd see a call that spends quite a few CPU cycles to get to the same result.)
However without an ability to read and write external memory would that be useful at all?
With no C calls, no built-ins and no luxury of Unsafe[Mutable][Raw][Buffer]Pointer the inner Swift itself doesn't give any ability to read/write arbitrary memory (unlike languages like C or Modula-2, perhaps many others, these are just two examples I know). Instead of solving this impossible puzzle I decided to turn the task inside out: let's this environment "allocate" memory bits and "provide" those bits to the outside world / host environment somehow. Writing to those bits done by the host environment would correspond to the app input (keyboard, mouse, microphone, camera, current time, gyroscope, network in, etc) and reading - to app output (screen, speaker, network out). "Allocating" memory is as easy as defining this global variable:
struct Heap {
var mem = Tuple4K<Byte>()
// 0x00, 16 bytes, magic bytes
// 0x10, 16 bytes, reserved
// 0x20, 2K bytes, screen pixels start, 1 bit, 128x128 bits (128x16 bytes)
// 0x820, 1K bytes, camera pixels start, 8 bit, 32x32 bytes (grayscale)
// ...
}
var heap = Heap()
Then just one bit of trickery left - finding the heap memory address from within the host environment: to facilitate that I have some magic byte signature at the beginning of the heap structure and looking for that pattern from within the host app to find the corresponding memory location, once the address is found - I/O between the app and the host environment is possible.
This is how the app looks like
// -parse-stdlib in flags and no `import Swift` here
private let screenWidth = XInt.x80
private let screenStride = XInt.x80
private let screenHeight = XInt.x80
private let cameraWidth = XInt.d32
private let cameraHeight = XInt.d32
private let cameraDataOffset = num(.x08, .x20)
private let screenDataOffset = XInt.d32
var heap = Heap()
struct Heap {
var mem = Tuple4K<Byte>()
// 0x00, 16 bytes, magic bytes
// 0x10, 16 bytes, reserved
// 0x20, 2K bytes, screen pixels start, 1 bit, 128x128 bits (128x16 bytes)
// 0x820, 1K bytes, camera pixels start, 8 bit, 32x32 bytes (grayscale)
mutating func initMagic() {
// magic bytes
mem[.x00] = .x86; mem[.x01] = .x73; mem[.x02] = .xF1; mem[.x03] = .xDE
mem[.x04] = .x63; mem[.x05] = .x19; mem[.x06] = .x50; mem[.x07] = .x27
mem[.x08] = .x66; mem[.x09] = .x39; mem[.x0A] = .x72; mem[.x0B] = .x04
mem[.x0C] = .x58; mem[.x0D] = .x29; mem[.x0E] = .x32; mem[.x0F] = .x46
}
}
func redrawScreen() {
var cameraOffset = cameraDataOffset
var screenOffset = screenDataOffset
var y = XInt()
while case .true = y < cameraHeight {
var x = XInt()
var screnLine = screenOffset
while case .true = x < cameraWidth {
func byteToBit(_ v: Byte) -> Bit {
v.bits.7
}
let a = byteToBit(heap.mem[cameraOffset + x]); x += .d1
let b = byteToBit(heap.mem[cameraOffset + x]); x += .d1
let c = byteToBit(heap.mem[cameraOffset + x]); x += .d1
let d = byteToBit(heap.mem[cameraOffset + x]); x += .d1
let e = byteToBit(heap.mem[cameraOffset + x]); x += .d1
let f = byteToBit(heap.mem[cameraOffset + x]); x += .d1
let g = byteToBit(heap.mem[cameraOffset + x]); x += .d1
let h = byteToBit(heap.mem[cameraOffset + x]); x += .d1
let byte = Byte(bits: (h, g, f, e, d, c, b, a))
heap.mem[screnLine] = byte
screnLine += .d1
}
screenOffset += .d16
y += .d1
cameraOffset += cameraWidth
}
}
public func mainProc() {
heap.initMagic()
}
To make the app more challenging: the screen is 1-bits per pixel (128x128 pixels), and the camera data is 8bpp (32x32 tiny image). The app converts from grayscale pixels to b&w pixels and draws the result:
It's only 32x32 b&w with no dithering or error diffusion, so hopefully with a bit of imagination you could see me turning around the room and waving 