117 lines
3.6 KiB
TypeScript
117 lines
3.6 KiB
TypeScript
import bit, { Bit } from "./bit"
|
|
import { range, zip } from "lodash"
|
|
import { Add, Max } from "math-types"
|
|
|
|
|
|
export interface Word<Width extends number> {
|
|
concat<OtherWidth extends number>(other: Word<OtherWidth>): Word<Add<Width, OtherWidth>>
|
|
toNumber(): number
|
|
toString(): string
|
|
plus: <OtherWidth extends number>(other: Word<OtherWidth>) => { sum: Word<Max<Width, OtherWidth>>, carry: Bit }
|
|
bits: Bit[] & { length: Width }
|
|
subword: <Width extends number>(start: number, length?: Width) => Word<Width>
|
|
equals: (word?: Word<number>) => boolean
|
|
}
|
|
|
|
type FixedLengthArray<T, Length extends number> = T[] & { length: Length }
|
|
|
|
export function wordFromBits<const Width extends number, const BitArray extends FixedLengthArray<Bit, Width>>(bits: BitArray): Word<BitArray['length']> {
|
|
|
|
function plus<OtherWidth extends number>(other: Word<OtherWidth>) {
|
|
const newBits = addBits(bits, other.bits)
|
|
|
|
return {
|
|
sum: wordFromBits(newBits.bits as FixedLengthArray<Bit, Max<Width, OtherWidth>>) as Word<Max<Width, OtherWidth>>,
|
|
carry: newBits.carry
|
|
}
|
|
}
|
|
|
|
function subword(start: number, length?: number) {
|
|
return wordFromBits(bits.slice(start, length !== undefined ? start + length : undefined))
|
|
}
|
|
|
|
function concat<OtherWidth extends number>(other: Word<OtherWidth>) {
|
|
return wordFromBits([...bits, ...other.bits])
|
|
}
|
|
|
|
function equals(other?: Word<number>) {
|
|
return other !== undefined
|
|
&& other.bits.length === bits.length
|
|
&& other.bits.every((otherBit, index) => bits[index].equals(otherBit))
|
|
}
|
|
|
|
function toNumber() {
|
|
return Number.parseInt(bits.map(bit => bit.value).join(""), 2)
|
|
}
|
|
|
|
function toString() {
|
|
return bits.map(bit => bit.value).join("")
|
|
}
|
|
|
|
return {
|
|
plus,
|
|
subword,
|
|
concat,
|
|
bits,
|
|
equals,
|
|
toNumber,
|
|
toString
|
|
} as Word<Width>
|
|
}
|
|
|
|
export function wordFromNumber(source: number, length?: number) {
|
|
const bitArray = source.toString(2).split("").map(char => bit(Number.parseInt(char) as 0 | 1))
|
|
const paddedBitArray = length === undefined ? bitArray : zeroPad(bitArray, length)
|
|
|
|
return wordFromBits(paddedBitArray)
|
|
}
|
|
|
|
export function wordFromString(source: string) {
|
|
const bitArray = source.split("").map(char => bit(Number.parseInt(char) as 0 | 1))
|
|
|
|
return wordFromBits(bitArray)
|
|
}
|
|
|
|
function addBits(bits: Bit[], otherBits: Bit[]) {
|
|
const resultLength = Math.max(bits.length, otherBits.length)
|
|
const paddedBits = zeroPad(bits, resultLength)
|
|
const paddedOtherBits = zeroPad(otherBits, resultLength)
|
|
|
|
const pairedBits = zip(paddedBits, paddedOtherBits) as [Bit, Bit][]
|
|
|
|
const sumResults = pairedBits.reduceRight<SumResult>(({bits, carry}, [a, b]) => {
|
|
const aPlusB = a.add(b)
|
|
const aPlusBPlusCarry = aPlusB.ones.add(carry)
|
|
const thisCarry = aPlusB.carry.add(aPlusBPlusCarry.carry).ones
|
|
|
|
bits.splice(0, 0, aPlusBPlusCarry.ones)
|
|
|
|
return sumResult(bits, thisCarry)
|
|
}, sumResult([], bit(0)))
|
|
|
|
|
|
return sumResults
|
|
}
|
|
|
|
function zeroPad(array: Bit[], length: number) {
|
|
return [...Array(length - array.length).fill(bit(0)), ...array] as Bit[]
|
|
}
|
|
|
|
|
|
interface SumResult {
|
|
bits: Bit[]
|
|
carry: Bit
|
|
}
|
|
|
|
function sumResult(bits: Bit[], carry: Bit) {
|
|
return {
|
|
bits: bits,
|
|
carry
|
|
}
|
|
}
|
|
|
|
export function emptyWord<Width extends number>(width: Width): Word<Width> {
|
|
const bits = range(0, width).map(() => bit(0)) as Bit[] & { length: Width }
|
|
return wordFromBits(bits)
|
|
}
|