Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 40 ยท Projects

Project: A String Toolkit

Build a string library in toy assembly: strlen, strcmp, strcpy, upper, reverse, atoi and itoa, all sharing one calling convention, with tests.

C's standard library hides a lot of small loops: strlen, strcmp, atoi, toupper. Each is a few lines of assembly, and writing them yourself teaches three skills at once: walking memory byte by byte, handling edge cases (the empty string, the minus sign, the character that is not a digit), and making routines that call each other without trampling each other's registers. This project builds seven of them as a small library for the toy CPU, with tests.

You should know strings and byte processing, arrays and addressing, CALL and RET and the idea of a calling convention. The code runs on the toy CPU from Meet the Toy CPU. Every TryIt includes the interpreter and the library, so each one is self-contained and you can change any routine and rerun.

Strings in memory

A C string is a run of characters ended by a zero value, the terminator. The routines never store the length; they find the end by looking for the zero. In real memory each character is one byte. The toy CPU gives every address one whole value, so our strings use one character per memory cell, which keeps the lesson about the logic and not about byte packing. The character 'A' is stored as the number 65, 'a' as 97, '0' as 48.

flowchart LR
  A["0x2000<br/>72 (H)"] --> B["0x2001<br/>105 (i)"] --> C["0x2002<br/>0 (end)"]

The string "Hi" occupies three cells; the zero tells every routine where to stop.

Two small JavaScript helpers connect the toy memory to the outside world: store writes a JavaScript string into memory (plus the terminator) and fetch reads one back. They are not part of the "program"; they are the test harness.

The calling convention

With only six general registers, who may change what must be written down. Our toolkit follows a simplified version of the rules real platforms use (Calling Conventions):

  • Arguments come in rdi (first) and rsi (second). The result returns in rax.
  • Scratch registers: a routine may change rax, rcx and rdx freely. Callers must not expect them to survive a call.
  • Preserved register: rbx. A routine that uses rbx must push it on entry and pop it before returning, so the caller's value comes back unchanged. That is what callee-saved means.
  • rdi and rsi normally survive the call too, because the loops index from them ([rdi+rcx]) instead of moving them. The one exception is itoa, which consumes rdi as it divides the number down.
flowchart TD
  itoa["itoa"] --> reverse["reverse"]
  reverse --> strlen["strlen"]
  atoi["atoi"]
  strcmp["strcmp"]
  upper["upper"]
  strcpy["strcpy"]

itoa builds the digits backwards and calls reverse, which calls strlen: routines are layered, and every layer must respect the convention.

The design choice to index with [rdi+rcx] rather than increment rdi matters. A function that walks a string by incrementing its argument register hands the caller a changed pointer; a function that keeps rdi fixed and counts in rcx leaves it intact, so the caller can pass the same pointer to the next call.

The library

The routines below are the whole toolkit. Read it top to bottom once: each routine is a short loop, and the comments say what the registers hold.

  • strlen: counts cells until the zero.
  • strcmp: compares cell by cell. It returns 0 for equal strings, otherwise the difference of the first pair of characters that differ (negative if the first string sorts earlier). It stops at the zero, so a string that is a prefix of another compares as smaller.
  • strcpy: copies including the terminator.
  • upper: converts a to z to uppercase in place by subtracting 32, which works because ASCII lowercase letters sit exactly 32 above their capitals.

The first test run uses only these four on a few strings.

JS strlen, strcmp, upper

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The first number, 12, is the length. The next is 32, the distance between 'w' (119) and 'W' (87); swapping the arguments gives -32; identical strings give 0; and "Hello" against "Hello, world" gives the negative of the first extra character, ',' (44), because at index 5 the first string has the terminator 0 and the second has 44. This is the same difference convention that C's strcmp documents loosely ("negative, zero or positive"): rely on the sign, not the exact value.

reverse, atoi and itoa

reverse swaps characters from both ends toward the middle with two indexes. It calls strlen, which needs a free rax and rcx, and it uses rbx as a temporary, so it demonstrates the convention: push rbx on entry, pop rbx on exit. It also guards the empty string. Without that check, dec rdx on a length of 0 wraps around to 4,294,967,295 and the loop would "swap" far-away memory, a classic unsigned-underflow bug; here the jz skips the whole loop.

atoi (ASCII to integer) multiplies the running result by 10 and adds each digit, where a digit is character - 48. One subtraction does both the conversion and the validity test: any character below '0' wraps to a huge unsigned value, and any above '9' is bigger than 9, so a single cmp rdx, 9 then ja rejects everything that is not a digit. It stops at the first non-digit, so "42abc" gives 42, and handles one leading minus.

itoa (integer to ASCII) is the reverse trip. The toy CPU has no divide instruction, so it divides by 10 the slow way, counting how many 10s can be subtracted. The remainder is the last digit and the quotient is what is left to convert. Digits come out last-first, so the routine ends by calling reverse on the buffer. It is a good example of building a bigger routine from a smaller one.

JS reverse, atoi, itoa and edge cases

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Look at the instruction counts for itoa: 7 takes 41 instructions but 12345 takes thousands. Dividing by repeated subtraction costs work proportional to the quotient, which is why real CPUs have a divide instruction (div, udiv) and why compilers replace division by a constant with a multiply and shifts. The toolkit stays correct; it is merely slow for large numbers, a trade you can now see in numbers.

Composing routines: a palindrome checker

Real programs combine small routines. A word is a palindrome if it reads the same backwards. With the toolkit this is three calls: strcpy the word into a scratch buffer, reverse the copy, strcmp the copy against the original. A result of 0 means palindrome. The test needs to leave the original untouched, which is why it copies first.

The same TryIt also checks the convention itself. It stores a marker, 1234, in rbx before each call and prints rbx after; if any routine forgot to save and restore rbx, the marker would change. A convention is only a promise until a test enforces it.

JS A palindrome checker and a convention test

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The empty string counts as a palindrome and so does a single letter, which is why the routines' edge cases matter: both rely on reverse doing nothing and strcmp seeing two zeros immediately. If you delete push rbx/pop rbx from reverse and rerun the second half, the report flips to CLOBBERED for reverse (and for itoa, which calls it): a missing save/restore is invisible in the routine's own result and shows up only in a caller's variable, which is exactly why such bugs are hard to find without a test like this one.

What changes on real hardware

On x86-64 System V the arguments arrive in rdi and rsi, the result leaves in rax, and rbx is callee-saved: our convention was chosen to mirror it. Real strings are bytes, so the loads become movzx eax, BYTE PTR [rdi+rcx] and the store of one character is mov BYTE PTR [rdi+rcx], al. Libraries compare a whole machine word or a 16 or 32-byte vector register at a time, using SIMD instructions to look for a zero byte in many characters at once, so strlen in a real C library is much faster than the one-character loop here. The logic you wrote is the same.

Ideas to extend it

  • Add strcat (append one string to another) using strlen and strcpy.
  • Make strcmp case-insensitive by converting both characters to lowercase before comparing.
  • Add lower, and isdigit (using the same sub 48, cmp 9, ja trick).
  • Make itoa handle negative numbers by writing a minus and negating.
  • Replace the subtraction loop in itoa with a binary long division using shifts.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does strcmp return in this toolkit when the first difference is 'w' versus 'W'?

    strcmp returns first - second at the first position that differs. 119 - 87 = 32. Callers should rely only on the sign, not the exact number.
  2. 2. Why must reverse begin with push rbx and end with pop rbx?

    The convention promises that rbx survives a call. A routine that wants to use it for its own purposes has to save the caller's value first and restore it before returning.
  3. 3. How does atoi reject a character that is not a digit with only one compare?

    After sub rdx, 48 a real digit is 0..9. A smaller character wraps around to a very large unsigned value, so cmp rdx, 9 followed by ja (unsigned above) catches both sides.
  4. 4. Why does reverse test for an empty string before the loop?

    dec on 0 gives 4,294,967,295 in an unsigned 32-bit register, and cmp/jae would not stop the loop. Checking length 0 first avoids the underflow.
  5. 5. Why does itoa call reverse at the end?

    Dividing by 10 repeatedly yields the last digit first. The buffer therefore holds the digits in reverse order and must be flipped.

Summary

  • A C string is a run of characters ended by a 0; every routine finds the end by scanning for it.
  • Agree on a calling convention first: arguments in rdi/rsi, result in rax, scratch registers rax, rcx, rdx, preserved register rbx (saved with push and pop).
  • Index from a fixed base ([rdi+rcx]) rather than moving the argument register, so the caller's pointer survives.
  • Edge cases decide correctness: the empty string, the minus sign, non-digit input and unsigned underflow.
  • One subtract-and-compare turns "is this a digit?" and "what is its value?" into a single test.
  • Build larger routines from smaller ones (itoa calls reverse, which calls strlen) and test the convention, not just the results.

Next: replace the toy CPU's engine with your own in Project: Build Your Own Tiny CPU Emulator.