3c's Problem

3c_problem.py

#!usr/bin/env python3

from dataclasses import dataclass
from math import log2, floor
from typing import cast, Set

if __name__ == '__main__':
    n_set_, n_blk_, n_sz_, cols = '# of total   sets: ', '# of total blocks: ', 'block size in bytes: ', 60
    n_set = int(input(n_set_))
    n_blk = int(input(n_blk_))
    n_sz = int(input(n_sz_))
    n_way = n_blk // n_set
    print()

    print('-' * (cols//2))
    print(f'{n_set_}{n_set}')
    print(f'{n_blk_}{n_blk}')
    print(f'# of total   ways: {n_way}')
    print(f'{n_sz_}{n_sz}')
    print(f'cache size in bytes: {n_blk*n_sz}')
    print()

    print('-' * cols)

    @dataclass
    class Data:
        addr: int
        inf: bool = False
        fa: bool = False
        sa: bool = False
        addr_of_ev: 'int|None' = None

    data: 'list[Data]' = []
    while ...:
        inp = input(f'addr #{len(data)+1} (leave blank to start): ')
        if not inp: break
        data.append(Data(addr=int(inp, 0)))
        print(f'addr #{len(data)}: {hex(data[-1].addr)}\n')
    print()

    # infinite
    blk_i: 'Set[int]' = set()
    for d in data:
        tag = d.addr // n_sz
        d.inf = tag in blk_i
        blk_i.add(tag)
    del blk_i

    # f. a.
    blk_f: 'list[int]' = []
    for d in data:
        tag = d.addr // n_sz
        if tag in blk_f:
            d.fa = True
            blk_f.remove(tag)
            blk_f.append(tag)
        else:
            d.fa = False
            blk_f.append(tag)
            if len(blk_f) > n_blk:
                del blk_f[0]
    del blk_f

    # s. a.
    @dataclass
    class LruData:
        v: bool
        lru: int
        data: Data

    sets: 'list[list[LruData]]' = [[LruData(False, 0, Data(0)) for _ in range(n_way)] for _ in range(n_set)]
    for d in data:
        d.sa = False
        tag = d.addr // n_sz
        set_i = tag % n_set
        blks = sets[set_i]
        done = False
        for blk in blks:
            if not blk.v:
                for blk_ in blks:
                    if blk_.v: blk_.lru -= 1
                blk.v, blk.lru, blk.data, done = True, n_way - 1, d, True
                break
            elif tag == blk.data.addr // n_sz:
                for blk_ in blks:
                    if blk_.lru > blk.lru: blk_.lru -= 1
                d.sa, blk.lru, blk.data, done = True, n_way - 1, d, True
                break

        if done: continue
        blk = min(blks, key=lambda x: x.lru)
        d.addr_of_ev = blk.data.addr
        if (blk.lru != 0): raise RuntimeError(blk.lru)
        for blk_ in blks:
            if blk_.lru > blk.lru: blk_.lru -= 1
        blk.lru, blk.data = n_way - 1, d

    print('-' * cols)
    print()
    max_addr = max(data, key=lambda x: x.addr).addr
    max_addr_hexlen = max(4, len(hex(max_addr)))
    max_addr_binlen = max(4, len(bin(max_addr)))

    blk_bits, set_bits = floor(log2(n_sz)), floor(log2(n_set))
    tag_bits = max_addr_binlen - 2 - blk_bits - set_bits
    tag_of_ev_label = 'Addr of Evicted'
    print(
        f'{"ADDR".center(max_addr_hexlen)} | {"ADDR in Bin".center(max_addr_binlen+3)} | INF | F A | S A | {"3Cs".center(10)} | {tag_of_ev_label.center(max_addr_binlen+3)}'
    )
    print(f'{"-"*max_addr_hexlen}-|-{"-"*(max_addr_binlen+3)}-|-----|-----|-----|-{"-"*10}-|-{"-"*(max_addr_binlen+3)}')

    for d in data:
        addr, inf, fa, sa, ev = d.addr, d.inf, d.fa, d.sa, d.addr_of_ev
        addr_ = f'{addr:#0{max_addr_binlen}b}'
        addr_ = f'0b \x1b[93m{addr_[2:2+tag_bits]} \x1b[95m{addr_[2+tag_bits:-blk_bits]} \x1b[96m{addr_[-blk_bits:]}\x1b[39m'
        print(end=f'{addr:#0{max_addr_hexlen}x} | {addr_}')
        for x in (inf, fa, sa):
            print(end=f' |  \x1b[{"92mH" if x else "91mM"}\x1b[39m ')
        print(end=' | \x1b[')
        if not inf:
            print(end='94mCompulsory')
        elif fa and not sa:
            print(end='93m Conflict ')
        elif not sa:
            print(end='95m Capacity ')
        else:
            print(end=f'92m{"-"*10}')
        if ev is None:
            addr_ = "-" * (max_addr_binlen+3)
        else:
            addr_ = f'{ev:#0{max_addr_binlen}b}'
            addr_ = f'0b \x1b[93m{addr_[2:2+tag_bits]} \x1b[95m{addr_[2+tag_bits:-blk_bits]} \x1b[96m{addr_[-blk_bits:]}\x1b[39m'
        print(f'\x1b[39m | {addr_}')
    print()
    print()

    print('-' * cols)
    for i, set in enumerate(sets):
        for j, blk in enumerate(set):
            addr_ = f'{blk.data.addr:#0{max_addr_binlen}b}'
            addr_ = f'0b \x1b[93m{addr_[2:2+tag_bits]} \x1b[95m{addr_[2+tag_bits:-blk_bits]} \x1b[96m{addr_[-blk_bits:]}\x1b[39m'
            print(f'Set {i} Way {j} Addr: {addr_}')
    print()
'''
2
4
16
0xdd5
0x1f07
0x2ae
0x509
0x2edf
0x1f0f
0x1f01
0x48d7
0xdda
0x380




'''