Project Logs

Collapse

• Primer: recursive Fibonacci

  Pavel • 06/03/2026 at 14:11 • 0 comments

  In this log I'll describe a small textbook program to find N'th Fibonacci number, as implemented on my ECM-16/TTL CPU architecture, using the emulation I created recently.

  Here is short video of process at 30 Hz clock rate:

  -------------

  Now, here is the program how it would be written in C:

  int fib(N) {
      if (N > 1) {
          return fib(N - 1) + fib(N - 2);
      }
  
      return 1;
  }
  
  void main() {
      int N = 5;
      int F = fib(N);
  }

  It is very small and uses recursion extensively to find the N'th Fibonacci number very inefficiently. It serves only as demonstration of machine's ability to be able to call functions recursively, and this arguably a big part of Turing completeness proof of the instruction set.

  Now, the program above is written in a way that does not output the result anywhere, there is no printf() or the like. I did it deliberately, as for now the emulation does not have any I/O except of rudimentary DMA that can be used to write values directly into the memory. On the other hand, all the registers and memory are visible while the emulation is running, and one of the registers can be chosen to hold output value, and thus the result could be read.

  To be able to run this program, it should be compiled and assembled, and due to lack of both compiler and assembler, this is to be done manually.

  First, here is C-like code that has flow which is closer to what the assembly program will look like:

  void main() {
      int N = 5;       // r3
      int F = fib(N);  // r4
  }
  
  int fib(N) {
      int n = N;        // r0
      if (n == 0) {
          return 1;
      }
  
      n = n - 1;
      if (n == 0) {
          return 1;
      }
      int a = fib(n);   // r6, calculating fib(N-1)
  
      n = N - 2;
      int b = fib(n);   // r7, calculating fib(N-2)
  
      return a + b;     // r0 = r6 + r7
  }

   This is the same program, but more verbose. All the variables inside the functions are mapped to CPU registers (shown in comments), while function parameters are passed via stack.

  Following is the listing of this program written in my assembly, together with machine code values obtained using this table. I added comments so the code could be followed through. After each machine word there is an address in memory where it resides (hexadecimal). All jumps are PC-relative. All data loads/stores are relative to Stack Pointer. The labels are started with underscores. 

  LDi SP 0x400    ;initialize stack
  ;   0x3a00, // 0
  ;   0x0400, // 2 
  JSR _main       ;start main function
  ;   0x1f01, // 4
  JMP -2          ;endless loop == halt execution
  ;   0x107f, // 6
  
  _main:      // #0x08 = 8(dec)
  LDi r3 0x5      ;initialize N
  ;   0x3300, // 8
  ;   0x0005, // a
  ST r3 (SP)+[-2] ;push r3, argument for _fib
  ;   0x73bf, // c
  ;   0xfffe, // e
  JSR _fib        ;calculate result with fib
  ;   0x1f04, // 10
  ADDp SP 2       ;adjust SP, discarding _fib's arg
  ;   0x0a01, // 12
  MOV r4 r0       ;save result to r4 (F)
  ;   0x2400, // 14
  LD PC (SP)[4]+  ;pop PC, return from _main
  ;   0x68a8, // 16
  ;   0x0004, // 18
  
  _fib:       // #0x1A = 26(dec)
  LD r0 (SP)[2]   ;load argument into r0
  ;   0x6038, // 1a
  ;   0x0004, // 1c
  ADD r0 0x0      ;test if it zero
  ;   0xc000, // 1e
  JZ _put_one 
  ;   0x1119, // 20
  SUB r0 0x0      ;test if it is 1
  ;   0xc801, // 22
  JZ _put_one
  ;   0x1117, // 24
  ST r6 (SP)+[-2] ;push r6 to preserve for caller
  ;   0x76bf, // 26
  ;   0xfffe, // 28
  ST r7 (SP)+[-2] ;push r7 to preserve for caller
  ;   0x77bf, // 2a
  ;   0xfffe, // 2c
  ST r0 (SP)+[-2] ;push r0, arg for call
  ;   0x70bf, // 2e
  ;   0xfffe, // 30
  JSR _fib        ;calling fib(n-1)
  ;   0x1f73, // 32
  ADDp SP 2       ;adjust SP, discarding _fib's arg
  ;   0x0a01, // 34
  MOV r6 r0       ;save fib(n-1) result to r6
  ;   0x2600, // 36
  LD r0 (SP)[8]   ;load argument value
                  ;offset is +4(stored PC)+4(stored r6,r7)=+8
  ;   0x6038, // 38
  ;   0x0008, // 3a
  SUB r0 0x2      ;calculate n-2
  ;   0xc802, // 3c
  ST r0 (SP)+[-2] ;
  ;   0x70bf, // 3e
  ;   0xfffe, // 40
  JSR _fib        ;calling fib(n-2)
  ;   0x1f6b, // 42
  ADDp SP 2       ;adjust SP, discarding _fib's arg
  ;   0x0a01, // 44
  MOV r7 r0       ;save fib(n-2) result to r7
  ;   0x2700, // 46
  ADD r0 r6 r7    ;calculate fib(n-1) + fib(n-2)
  ;   0x8067, // 48
  LD r7 (SP)[2]+  ;pop preserved r7 
  ;   0x67a8, // 4a
  ;   0x0002, // 4c
  LD r6 (SP)[2]+ ;pop preserved...

  Read more »

• Emulation in software

  Pavel • 05/31/2026 at 13:31 • 0 comments

  A month ago I decided to create a small rtl emulation of my CPU design, to better grasp high-level view of it, and test some design changes and instruction sequences faster. This simplification was needed, because the model in Digital simulation became too complex and had some bugs with timings that I couldn't fix. Also this complexity would make revision of micro-operation sequencing very difficult.

  I thought the task would be simple, and take a week or two, as first idea was to make a list of registers and write some functions that would juggle around values between them. Turned up that it took more time, mostly because I ended up with more thorough simulation, with data structures for registers and busses, and sequential logic for data propagation which itself is often a parallel process. The ALU is just a functional description, but all the plumbing (busses, selectors) between functional blocks are accounted for in this emulation.

  Fair bit of time took the re-drawing of RTL scheme, and figuring out the correct data transfers for microinstructions. While doing so I found similarities between several states, and attempted to condense them. This made FSM to contain fewer states, but state transition logic became more complex.

  Here is part of the process of figuring out correct paths for data between registers for particular microinstructions:

  During this process, I also updated instruction encodings somewhat, and the RTL scheme itself, though marginally.

  ----------------

  I wrote the emulation in C, and for the interface used ncurses library, which proved to be very easy to use, and made me able to concentrate mostly on the workings of emulated CPU, and not spend too much effort figuring out the presentation.

  As of the time of writing, current emulation implements most of the instructions, in particular, ALU, memory accesses with all modes, MOVes and jumps (including JSR). Yet to be added are Address Arithmetic, interrupt related instructions and some other miscellaneous ones.

  Currently, running emulation looks like this (screenshot):

  I think in time I will make it slightly more colourful, but for now it is already very informative. It exposes most of the CPU insides, like register values, a selection of bus values, the control logic state, and control line activation pattern (microinstruction word), and all of the memory (1kB) at a glance. This proved very helpful in troubleshooting this emulation, as well as the little test programs I wrote for it.

  It is trivially possible to make the emulation with any memory size up to 16 megabytes, but more than 1kB will be hard to impossible to show at once. And for testing purposes current memory size is quite adequate.

  ---------

  For now, I am manually assembling the code, as previous assembler version is long been neglected, and as instruction encoding was changed, does not output correct code anyway. When instruction set will be finalized, the assembler will be updated, or rewritten outright.

• Interrupt handling

  Pavel • 05/26/2026 at 13:44 • 0 comments

  I think I finally got it about how to treat interrupts. 

  Well, I thought so 5 years ago (and described the mechanism in the old log). Now, rethinking again, after having read the handbook on pdp-11/40 processor and ARM2 databook, I found out that the dedicated Instruction Vector register is not needed, this address can be supplied directly from EINT instruction.

  On the other hand the notion that EINT can be just a jump to subroutine, only with a pre-defined address is missing one component - the saving of current status. Previously I thought that it could be done with additional instruction, but on closer look, this makes some things awkward. So, the EINT should push to stack the SR together with PC. And, as I added the TMP ALU register, that is used as extended carry in some shift operations, it is also should be pushed to stack. In total, 4 words need to be saved, 2 for return address, and SR together with TMP. This now also demands the addition of IRET instruction which properly pops PC, SR and TMP all together so that execution can continue after interrupt as if nothing happened.

  Also I think that making the CPU be able to support two modes can be beneficial, and I want to explore this territory. For this to work, at minimum there is a need for additional Stack Pointer, which can be integrated into current design without much pain.

• Update to RTL scheme

  Pavel • 05/16/2026 at 12:22 • 0 comments

  While trying to accomodate the features provided by funnel shifter, and changing address bus width to 24 bits, I started to look closely into the current Register Transfer scheme, and started to update it. I shuffled around parts of it for more clarity, and for including new features -- I've redrawn the scheme several times by hand, and after having a good variant, I drawn the scheme in Excel (this provides grid, and thus it is easier to make aligned drawings using different cell borders and applying different border styles to them).

  Here is the result:

  Compressed version:

  -----------

  Full resolution:

  This is quite a detailed scheme, it is advisable to click full-scale by click on the above image.

  --------

  This updated scheme is also part of the effort to create an emulation of this CPU, about which I'll write in the next log.

  Such scheme makes for easier understanding of CPU inner workings, and devising microinstruction sequences for all the different instructions. The image presented is intended to be printed out in several copies for tracing out data propagation and capturing the proper pattern of micro instruction bits. I did the same thing 4 years ago on previous version of RTL scheme, but as I modified it, I need to redo this thing again.

• State Machine and operation sequencing

  Pavel • 05/01/2026 at 14:27 • 0 comments

  The last time I made update to FSM design, it turned out working ok. But, returning to it now, I find that there is still room for improvement, especially regarding overall sequencing of micro-instruction stages.

  The overall sequence is as following: at the falling clock edge a new state is entered, and appropriate signals for selectors, bus drivers and register addresses to be written (write enable lines) to percolate through combinational logic circuits. Then, at the rising clock edge, all the registers (which have their write enable signals HIGH) get new data latched. Regarding data processing, as in example below for ALU instruction: the instruction itself has several bits that are used almost directly to set the ALU to do what instruction says, so the operation begins when there is still Fetch state. This gives time until next rising edge for it to output its result. On the other hand, between starting memory access operation (fetching instruction) and latching the value there is only half a cycle, which makes addressing very constrained by time available. The other half cycle for memory access is idle.

  Here is the example timing diagram showing this:

  ------------

  I think, there is a way to make memory access time a full cycle, with moving setting of the select and enable signals at the rising edge. This will make them seem to be at the same time as latching, but in fact, the latching will be for values from previous micro-op, and there will be delay between rising clock edge and update to select/enable signals because they will be delayed by intervening combinational logic.

  ----------

  
  New clock cycle starts right after the rizing edge, when all registers have latched previous values. These values now determine what will go on in this cycle.
  The state transitions should be somewhat offset from the main clock rising edge. Previously it was done via making these transitions go on clock falling edge. This works, but for some micro-ops, like fetch, it leaves only half of the cycle to put address to memory bus, and retrieve the stored value. As
  memory has latency in range 50-120ns (depending on IC used), this places a constraint on the overall frequency of operation. The other half cycle of fetch is used for decoding the fetched instruction opcode. As this is pretty fast (a couple of gate delays), most of the half-cycle gets unused.
  
  

  Now, the new scheme strives to reduce the time for opcode decoding to a minimum, and thus use most of the clock cycle for accessing the memory. This also moves the decode part a bit.

  
  The general scheme is:

  Previously, the fetch and decode parts were fused together into F1 state. A new
  proposal is for fusion of decode and execute phases. At the clock cycle start, Fetch enables the PC value to Address bus, and the Address Adder outputs PC + 2 to Memory Pointers (with PC selected for latch). At the next rising clock edge, the IR is latched with value output from Memory, and PC is latched value output from Address Adder.

  On the next clock cycle is Decode fused with Execute. A newly latched value in
   Instruction Register is decoded, and the appropriate state is then activated.
  Signal from the newly activated State propagates to set the selectors, enables and latch addresses for particular microinstruction. The rizing clock edge concludes the cycle.

  Below is new waveform:

  ----------

  This, along with tweaks to ISA prompts reevaluation and new update to FSM, on which I am working now.

• Funnel Shifter 16-bit diagram

  Pavel • 04/27/2026 at 17:31 • 0 comments

  I had scaled up the model shifter described in previous log to the full 16 bit width. Along the way I found some inefficiencies in design, and corrected for them -- this made circuit to behave slightly differently in marginal ways, but overall change is positive due to some irregularities weeded out. This is mostly theoretical for now, as the circuit exists mostly as various diagrams I drawn while designing it; also I created the Verilog description, flashed it onto FPGA and tested -- it turned out to work correctly.

  Here is functional diagram of this circuit:

  As was written in previous log, this shifter makes use of additional register as source of data, the register is called TEMP, and it is outside of main Register File. This additional register is used only in subset of operations this shifter is capable of, namely, the Rotate Through Temp op (which is like Rotate Through Carry, but extended to several bits at once), and Frame Shift, where a contigous 16-bit field is extracted from combined Src and TEMP registers.

  The Rotate Through Temp requires special circuit I called Magnitude Selector. It consists of 2 parts -- the circuit that takes in 4 lines defining rotation amount (1b, 2b, 4b and 8b) and outputs 16-bit value containing from 0 to 15 ones, like this:

  0:   0000 0000 0000 0000
  1:   1000 0000 0000 0000
  2:   1100 0000 0000 0000
  ...
  7:   1111 1110 0000 0000
  ... 
  15:  1111 1111 1111 1110

   through 16 lines; these lines, each ANDed with enable signal drive the muxes between 8b and 16b selectors. This makes it possible to swap a selected number of bits between TEMP register and shifted bits from Src register; the leftower bits of TEMP stay unaffected:

  This one is the more complex part of this whole circuit.

  I am thinking of adapting this design to using 74HC family logic, and juggling between wiring complexity and propagation delays, I think at least the last 3 stages should be condensed into one consisting of 8-to-1 muxes (74HC151). This seems more appropriate, as each bit should be switched separately for magnitude selection, and the 2-to-1 muxes (74HC157) are packaged in a way that switches 4 muxes by single select signal. 

  ------------------

  Although almost all diagrams I hand drawn, I found a cool website (with editor called svgbob) which turns ascii diagrams into svg images, facilitating line drawings. So the diagrams above were done using it.

• Funnel Shifter (4-bit model)

  Pavel • 03/13/2026 at 17:52 • 0 comments

  In previous post I wrote about planning to add a funnel shifter (an extended barrel shifter) to this CPU design. Now, I have designed a 4-bit prototype, and implemented it in FPGA, it has all the needed control signals, and performs all operations I intended it to perform. The 16-bit version would have more bits controlling shift amount, but other control signals will stay the same.

  What is the Funnel Shifter? 

  This is an extension of the Barrel Shifter, in a sense that it is 2 times wider than machine word (barrel shifter usually is the same width as word), and can manipulate data on 2 consecutive registers as if was one double-sized register, and extract the arbitrary word-sized bit field. Thus, it takes two words as input, and outputs a single word. In my implementation, there are some additional functions, and caveats.

  Here is the schematic I drawn (it is final, 7th version), which helped me in writing Verilog description:

  On the schematic, there is the funnel shifter itself, comprised of a bunch of 2:1 muxes with a little sprinkling of AND and OR gates,  as well as temporary register represented as 4 data flip flops r_A through r_D (blue squares). This register holds shifted-out bits that could be retrieved later, with special MOV operation, or used in consecutive operation to facilitate multi-word shifts/rotates.
  
  There are 5 types of shifting operations this circuit is capable of:
  1) regular shifts to the left or right;
  2) arithmetic shift right;
  3) rotate word right;
  4) rotate through N bits of temp register*;
  5) rotate double word.
  *This is expansion of Rotate Through Carry, but can use several bits from temp register.
  
  There are 4 control lines defining general operation (red, with inputs on top):
  A: Arithmetic shift;
  R: Rotate (for single-word rotation);
  T: Use the Temporary register;
  E: Extended rotation (rotate double-word, has effect only with T).
  
  There are also 3 control lines (golden-red, with inputs on the right) defining shift amount and direction (1b, 2b and 4b).
  
  The temporary register is supposed to be updated only for operations that have T signal high.
  
  As there are 4 control lines, there is 16 possible combinations, but not all of them are useful, and some of them are functionally duplicates. Out of them, 5 combinations are selected to provide 5 operations listed above. Of these, arithmetic shift and single word rotations need to be only to the right.
  
  
  Rationale for using special temporary register instead of second general purpose register:
  there is just not enough bits in instruction for encoding second source register address. I need to provide the source, the destination, and shift amount (or third register containing shift amount), and this is already 9 or 10 bits out of 16-bit instruction, 6 bits that are left are opcode. There is no way to have another 3 bits for yet another source register address.
  
  With global structure of this shifter proven on 4-bit model, the next now is to scale it to 16 bits.

• Plans for the near future

  Pavel • 03/07/2026 at 09:08 • 0 comments

  FPGA

  
  I already received my first FPGA board - Tang Nano 9k (it is presumably the best in terms of bang for the buck, with more than 8 thousand LUTs for slightly less than 20 USD, including shipping). The board itself is fairly small and have just a pair of buttons and 6 leds for user interaction, as well as fair number of pins. To have a more hands-on experience, I decided to make an extension board for it, which could also serve as test harness for CPU components implemented with this FPGA.
  And I already started my journey into Verilog, making small projects utilizing the prototype extension board mentioned above.

  -------------------

  ISA updates

  Now, to the CPU itself -- I am now working on some updates to ISA after a closer look of what I have to date. Mostly updates are concerning with redoing bit shifting circuitry, and some slight bit rearrangements in encoding the instructions for more clarity.
  I am also thinking about addressing, mostly if there is a need of making it 32 bits. In theory such big address space is good, but given the target speed and just physical availability of SRAM ICs, it looks like 24 bit for addresses would be enough (16MB). This also will make Address Adder narrower, and overall somewhat more manageable wiring for Address Unit. Implementation in FPGA somewhat relaxes this restriction, but I still want to eventually make the real physical processor using discrete logic chips, and this phase of implementing it on FPGA should strive to resemble the intended form as close as possible.

  -------------------

  Discussion of bit shifts and rotations

  Regarding shifting operations -- in current design there is a shifter circuit that can do 1-bit shift operations, and barrel rotator that is able to rotate bits in word to arbitrary amount in range 0..15 bits. The rotator was an afterthought, and was added mostly because there were unused slots in selector for ALU operations. The functionality and usefulness of this arrangement is questionable. Thus, returning after the years I had not had an attention to this project, I saw an opportunity of improvement in this regard -- to fuse shifter and rotator into one more complex circuit -- the Funnel Shifter, as I found afterwards it is called. This should be able to make arbitrary shifts and rotations in one cycle, and with additional temporary register there is possibility of extending these operations to multi-word shifts / rotations.
  Right now I am working on designing it, simulating, and this will be the first CPU part to be implemented on the FPGA.

  -------------------

  Plans for hardware build
  

  Afterwards I plan to build up the decoder FSM, ALU, registers and the rest of the CPU; It seems like this whole CPU can be mapped / implemented on the FPGA chip I have with room to spare, so in the end I will have a piece of functional hardware with which I can play further. The Verilog code I intend to write will also serve as blueprint for building with actual logic chips.

• A small update

  Pavel • 02/01/2026 at 07:06 • 0 comments

  Due to life's circumstances, I haven't been able to pursue this project as it is for the last 4 years, and it seems I won't be able to do so for a while yet.
  
  The dream of building my own CPU is not dead yet, so there will be a follow up on it soon (I hope).

  I found out recently there are inexpensive FPGAs available on AliExpress, so I've ordered one (Tang Nano 9k), and plan to play with it, at the same time finally learning Verilog, and then will try to implement architecture described in this project (with some modifications) on it. This will provide much more portable solution, definitely cheaper, though not a true discrete component cpu, but still something more tangible than software simulation.

• Memory map

  Pavel • 12/12/2022 at 19:57 • 0 comments

  The computer has 32-bit address bus, which provides address space of 4 Gigabytes of memory. This is quite big, taking into account that processor will run at frequencies in range of megahertz. It will take more than half an hour for PC to traverse from address zero to the top of this address space doing only NOPs (they take 2 clock cycles) when running at 4MHz. This is impractical in my opinion. Also, as I intend to use SRAM chips, it will be very big and very, very expensive build, which may not even be capable of work at such speeds reliably.

  ---

  So there will only be maximum of 16 Megabytes of SRAM (main RAM) installed -- for this only lowest 24 bits of address are needed.
  

  The main RAM address range will be from 0x0000.0000 up to 0x00FF.FFFF. This is just 1/256 of all the address space. 

  Maybe some time in the future I'll implement some sort of memory management with paging and ability to swap memory to permanent storage, and thus full address range could be utilized.

  These 16 MB are the lower memory.

  ---

  There will also be a chunk of address space where ROMs and I/O is mapped. For future proofing I decided to place it at the very top, in range from 0xFF00.0000 to 0xFFFF.FFFF.
  

  The first megabyte (0xFF00.0000--0xFF0F.FFFF) is reserved for ROMs, where system monitor and standard interrupt service routines are to be located.

  The last megabyte (0xFFF0.0000--0xFFFF.FFFF) is for Video RAM -- there 2 video buffers are to be located, they will be switching as described on this section of wiki article (page flipping). The two pages of VRAM will not necessary occupy a whole megabyte, I think that pages 128 kBytes each will be enough. These buffer pages will be on the very top of address space.

  The next to last megabyte (0xFFE0.0000--0xFFEF.FFFF) is to be reserved for various I/O ports, video control registers, palette and character table.

  ---

  All the addresses in between will be left unused, there are just so many of them.

  ---

  Graphical overview of the whole address space:

  +-------------------------------------+ FFFF FFFF
  |       ROMs, I/O, video RAM          |  16MB higher memory
  +-------------------------------------+ FF00 0000
  |                                     | FEFF FFFF
  ~       No hardware mapped here       ~
  ~  May be used for virtual addresses  ~
  |                                     | 0100 0000
  +-------------------------------------+ 00FF FFFF
  |             Main RAM                |  16MB lower memory
  +-------------------------------------+ 0000 0000
  

  ---

  Graphical overview of the higher memory:

  +-------------------------------------+ FFFF FFFF
  |              Video RAM              |  2 pages 128 kBytes each for display data
  +-------------------------------------+ FFE0 0000
  |                 I/O                 |  keyboard, PATA, UARTs etc. mapped here
  +-------------------------------------+ FFD0 0000
  |                                     |  unused
  +-------------------------------------+ FFC0 0000
  |                                     |  unused
  +-------------------------------------+ FFB0 0000
  |                                     |  unused
  +-------------------------------------+ FFA0 0000
  |                                     |  unused
  +-------------------------------------+ FF90 0000
  |                                     |  unused
  +-------------------------------------+ FF80 0000
  |                                     |  unused
  +-------------------------------------+ FF70 0000
  |                                     |  unused
  +-------------------------------------+ FF60 0000
  |                                     |  unused
  +-------------------------------------+ FF50 0000
  |                                     |  unused
  +-------------------------------------+ FF40 0000
  |                                     |  unused
  +-------------------------------------+ FF30 0000
  |                                     |  unused
  +-------------------------------------+ FF20 0000
  |                                     |  unused
  +-------------------------------------+ FF10 0000
  |                 ROMs                |  EEPROMs with system software (monitor, ISRs)
  +-------------------------------------+ FF00 0000
  |                                     | FEFF FFFF
  ~          virtual addresses          ~
  
  

  The ROMs and VRAM will not occupy whole Megabyte slots, but placed individually for ease of addressing.

  ---

  Graphical overview of the VRAM slot:

  +-------------------------------------+ FFFF FFFF
  |               page 1                |  
  |            (128 kBytes)             |  
  +-------------------------------------+ FFFD 0000
  |               page 0                |  
  |            (128 kBytes)             |  
  +-------------------------------------+ FFFC 0000
  |                                     |  
  |                                     |  unused
  +-------------------------------------+...

  Read more »

View all 55 project logs