RISC-V Assembly Part 6: Byte Order, Two's Complement, and Strings

# RISC-V Assembly Part 6: Byte Order, Two's Complement, and Strings

## CS 315 Computer Architecture

---

## Overview

Connecting high-level C to its underlying memory representation:

- Memory as a byte-addressable array
- How multi-byte integers are laid out (**endianness**)
- Why we use **two's complement** for signed integers
- **Sign extension** and **truncation**
- **C strings** as null-terminated byte arrays
- RISC-V `lb`/`sb` for byte-level access

---

## Learning Objectives

- Describe the processor/memory model (registers, PC, stack, heap, data, code)
- Explain byte-addressable memory and what a byte is
- Distinguish big-endian from little-endian; identify RISC-V's order
- Explain why two's complement won over sign-magnitude
- Negate a two's complement value using `invert(v) + 1`
- Widen with sign extension; narrow with truncation
- Represent C strings and walk them with `lb`/`sb`

---

## The Processor / Memory Model

<div class="mermaid">
flowchart LR
    subgraph CPU["Processor (CPU)"]
        REGS["Registers (x0-x31)"]
        PC["PC (program counter)"]
    end
    subgraph RAM["Memory (RAM)"]
        STACK["STACK"]
        HEAP["HEAP"]
        DATA["DATA"]
        CODE["CODE"]
    end
    REGS -- "store" --> RAM
    RAM -- "load" --> REGS
    PC -- "fetch" --> CODE
</div>

- Processor computes only on values in **registers**
- **Load/store** moves data between registers and RAM
- **PC** drives instruction fetch from the code region

---

## Memory Regions

| Region | What it holds | Grows |
|--------|---------------|-------|
| **Stack** | Call frames, local vars, saved regs | Down (toward lower addresses) |
| **Heap** | `malloc` allocations | Up (toward higher addresses) |
| **Data** | Global / static variables | Fixed |
| **Code** | Machine instructions | Fixed |

<div class="info-box">
Regardless of region: <strong>memory is just a long array of bytes</strong>.
</div>

---

## Memory Is Byte-Addressable

- The smallest addressable unit is a **byte** (8 bits)
- Every byte has a unique address: 0, 1, 2, ...
- Think of RAM as a giant `uint8_t` array

```text
addr:   ...  4    3    2    1    0
        +----+----+----+----+----+
byte:   |    |    |    |    |    |
        +----+----+----+----+----+
                                ^
                            1 byte = 8 bits
```

A single byte holds `0x00`–`0xFF` (256 values). Larger values span **consecutive bytes**.

---

## Load Width Matches Data Size

| C type | Bits | Bytes | RISC-V load |
|--------|------|-------|-------------|
| `char` / `uint8_t` | 8 | 1 | `lb` / `lbu` |
| `short` | 16 | 2 | `lh` / `lhu` |
| `int` / `uint32_t` | 32 | 4 | `lw` / `lwu` |
| `long` / pointer | 64 | 8 | `ld` |

**Key question:** If an `int` is 4 bytes, in what order are those bytes stored in memory?

---

## Endianness: The Problem

```c
int x = 0xFFAA1122;
```

The four bytes are: `0xFF  0xAA  0x11  0x22` (MSB to LSB).

They occupy addresses `&x`, `&x+1`, `&x+2`, `&x+3`. Which byte goes at the lowest address?

<div class="highlight-box">
Two conventions: <strong>big-endian</strong> (MSB first) vs <strong>little-endian</strong> (LSB first).
</div>

---

## Big-Endian vs Little-Endian

<div class="mermaid">
flowchart LR
    V["0xFFAA1122"] --> BE["Big-endian\nFF AA 11 22\n(MSB at lowest addr)"]
    V --> LE["Little-endian\n22 11 AA FF\n(LSB at lowest addr)"]
</div>

| Address | Big-endian | Little-endian |
|---------|-----------|---------------|
| `&x + 0` | `0xFF` (MSB) | `0x22` (LSB) |
| `&x + 1` | `0xAA` | `0x11` |
| `&x + 2` | `0x11` | `0xAA` |
| `&x + 3` | `0x22` (LSB) | `0xFF` (MSB) |

<div class="info-box">
<strong>RISC-V (and x86) are little-endian.</strong> The byte at the lowest address is the least significant byte.
</div>

---

## Detecting Endianness in C

```c
int x = 0xFFAA1122;
uint8_t *p = (uint8_t *)&x;  // reinterpret as byte array

printf("p[0] = 0x%02X\n", p[0]);  // 0x22 on little-endian
printf("p[1] = 0x%02X\n", p[1]);  // 0x11
printf("p[2] = 0x%02X\n", p[2]);  // 0xAA
printf("p[3] = 0x%02X\n", p[3]);  // 0xFF

if (p[0] == 0x22) printf("little-endian\n");
```

**Pointer cast note:** The address does not change. The _pointed-to type_ decides how many bytes to read when you dereference.

---

## Why Endianness Matters

Endianness is **invisible** within a single machine — store and load give you the same value.

It becomes visible when:

1. **Byte-level access** — casting `int *` to `char *` and reading individual bytes
2. **Networking** — machines with different byte orders exchange raw bytes

<div class="highlight-box">
Network protocols define <strong>network byte order</strong> (big-endian). Code converts to/from host order.
</div>

---

## Representing Signed Integers

Unsigned binary is easy: `0b1010` = 10. But how do we represent **negative** numbers?

Three candidates for 4-bit signed representation:

| Binary | Sign-Magnitude | Two's Complement |
|--------|----------------|------------------|
| `0000` | 0 | 0 |
| `0101` | +5 | +5 |
| `0111` | +7 | +7 |
| `1000` | **-0** | **-8** |
| `1101` | -5 | **-3** |
| `1111` | -7 | -1 |

---

## Sign-Magnitude: Two Problems

**Problem 1: Two zeros**
- `0000` = +0, `1000` = -0 (wasteful; equality checks are awkward)

**Problem 2: Addition is broken**

```text
  0 1 0 1   (+5)
+ 1 0 1 1   (-3 in sign-magnitude)
---------
  1 0 0 0 0  = 0 after dropping carry   WRONG! (should be 2)
```

Hardware would need special-case logic for every signed operation.

---

## Two's Complement Wins

Addition "just works" with the same hardware as unsigned:

```text
  0 1 0 1   (+5)
+ 1 1 0 1   (-3 in two's complement)
---------
1 0 0 1 0   drop carry out -> 0010 = 2   CORRECT!
```

**Why two's complement won:**
- **One zero** — range is `-8..+7` for 4 bits (not `-7..+7`)
- **MSB is still the sign bit** (0 = non-negative, 1 = negative)
- **Same adder circuit** handles positive and negative — no special cases

---

## 4-Bit Two's Complement Table

| Binary | Unsigned | Two's Complement |
|--------|----------|------------------|
| `0000` | 0 | 0 |
| `0001` | 1 | 1 |
| `0111` | 7 | 7 |
| `1000` | 8 | **-8** |
| `1001` | 9 | -7 |
| `1110` | 14 | -2 |
| `1111` | 15 | -1 |

Range for `n` bits: **-2^(n-1)** to **+2^(n-1) - 1**

---

## Negating a Two's Complement Value

**Recipe:** `negate(v) = invert(v) + 1`

Flip every bit, then add 1.

**+3 to -3 (4 bits):**

```text
 3  =  0011
       ↓ invert all bits
       1100
       ↓ add 1
-3  =  1101
```

**-3 back to +3 (same operation!):**

```text
-3  =  1101
       ↓ invert
       0010
       ↓ add 1
+3  =  0011
```

<div class="info-box">
<code>invert(v) + 1</code> is its own inverse — one procedure in both directions.
</div>

---

## Negation in C

```c
int8_t v = 3;
int8_t neg = ~v + 1;          // invert bits, add one
printf("%d\n", neg);          // -3
printf("0x%02X\n", (uint8_t)neg);  // 0xFD

// The compiler does the same for unary minus:
printf("%d\n", -v);           // -3
```

The unary `-` operator in C is exactly `invert + 1` under the hood.

---

## Changing Bit Width

When moving a value into a wider or narrower container, we must preserve the value **and** its sign.

**Widening (sign extension)**
- More bits needed
- Replicate the sign bit into all new high bits

</div>
<div>

**Narrowing (truncation)**
- Fewer bits needed
- Keep the low bits, discard the high bits

</div>
</div>

---

## Sign Extension

**Negative: `1101` (-3) from 4 bits to 8 bits**

Sign bit is `1` → fill new upper bits with `1`:

```text
4 bits:     1 1 0 1       (-3)
            ^ sign bit = 1
8 bits:  1 1 1 1 1 1 0 1  (-3)
```

**Positive: `0011` (+3) from 4 bits to 8 bits**

Sign bit is `0` → fill new upper bits with `0`:

```text
4 bits:     0 0 1 1       (+3)
8 bits:  0 0 0 0 0 0 1 1  (+3)
```

---

## Sign Extension Across Widths

The value `-3` at different widths:

| Width | Bits | Hex |
|-------|------|-----|
| 4 bits | `1101` | — |
| 8 bits | `1111 1101` | `0xFD` |
| 64 bits | `1111...1101` | `0xFFFFFFFFFFFFFFFD` |

<div class="highlight-box">
This is why Project 3's <code>unstruct</code> prints <code>-99</code> as <code>0xFFFFFFFFFFFFFF9D</code> — the negative value is sign-extended to 64 bits, filling the top with F's.
</div>

---

## lb vs lbu: Sign vs Zero Extension

<div class="info-box">
Sign extension is only correct for <strong>signed</strong> values.<br>
For <strong>unsigned</strong> values, use <strong>zero extension</strong> (fill new high bits with 0).
</div>

| Instruction | Extends | Use for |
|-------------|---------|---------|
| `lb` | Sign-extends | `char` (signed) |
| `lbu` | Zero-extends | `unsigned char` |
| `lh` | Sign-extends | `short` |
| `lhu` | Zero-extends | `unsigned short` |

Example: byte `0xFD` loaded with `lb` = `-3`; loaded with `lbu` = `253`.

---

## Sign Extension by Shifting

A common trick: shift left to the top, then **arithmetic shift right** back:

```c
int32_t v = 0b1110;    // we mean -2 as a 4-bit value
v = (v << 28) >> 28;   // shift to top, then SRA back
// v is now -2 (0xFFFFFFFE)
```

In RISC-V assembly use `srai` (arithmetic), not `srli` (logical) — `srli` would zero-fill and give the wrong answer for negatives.

---

## Truncation

Narrowing: **keep the low bits, discard the high bits**.

```c
int32_t big = -3;             // 0xFFFFFFFD
int8_t small = (int8_t)big;   // keep low 8 bits: 0xFD = -3   (OK)

int32_t huge = 300;           // 0x0000012C
int8_t tiny = (int8_t)huge;   // keep low 8 bits: 0x2C = 44   (WRONG!)
```

<div class="highlight-box">
Truncation is safe <strong>only when the value fits</strong> in the narrower type. 300 does not fit in <code>int8_t</code> (-128..127), so it wraps to 44.
</div>

---

## C Strings: Null-Terminated Byte Arrays

```c
char *s = "foo";
```

`"foo"` occupies **4 bytes** in memory:

```text
   s[3]  |  '\0'  0x00  |  <- terminator (value 0)
   s[2]  |  'o'   0x6F  |
   s[1]  |  'o'   0x6F  |
   s[0]  |  'f'   0x66  |  <- s points here
```

- Each character holds its **ASCII code**
- `'\0'` is the integer zero — NOT the digit `'0'` (which is `0x30`)
- No separate length field — the null byte **is** how code knows the end

---

## Using lb / sb for Strings

- `lb t0, 0(a0)` — read one byte from memory, **sign-extend** into all 64 bits of `t0`
- `sb t0, 0(a0)` — write only the **low 8 bits** of `t0` to memory

```text
register t0 (64 bits)
+------------------------------------+--------+
|  sign-extended upper 56 bits       | byte 0 |
+------------------------------------+--------+
                                      \_______/
                                      lb writes here / sb reads here
```

Use `lbu` for unsigned bytes (zero-extend instead of sign-extend).

---

## String Length in C

```c
int my_strlen(char *s) {
    int len = 0;
    while (*s != '\0') {  // stop at null byte
        len++;
        s++;              // advance one byte
    }
    return len;
}
```

- Walk the pointer until the null terminator
- Each character is **1 byte**, so `s++` advances by 1

---

## String Length in RISC-V Assembly

```asm
# int my_strlen(char *s)   a0 = s  ->  returns length in a0
my_strlen:
    li   t0, 0              # t0 = len = 0
strlen_loop:
    lb   t1, 0(a0)          # t1 = *s (current byte)
    beq  t1, zero, strlen_done   # if byte == '\0', stop
    addi t0, t0, 1          # len++
    addi a0, a0, 1          # s++ (one byte at a time)
    j    strlen_loop
strlen_done:
    mv   a0, t0             # return value in a0
    ret
```

- Advance pointer by **1** (bytes, not words)
- Return value goes in `a0` per calling convention

---

## String Copy in RISC-V Assembly

```asm
# void my_strcpy(char *dst, char *src)   a0=dst, a1=src
my_strcpy:
    li   t2, 0              # i = 0
strcpy_loop:
    add  t3, a1, t2         # t3 = &src[i]
    lb   t1, 0(t3)          # t1 = src[i]
    add  t4, a0, t2         # t4 = &dst[i]
    sb   t1, 0(t4)          # dst[i] = src[i]
    beq  t1, zero, strcpy_done  # stop AFTER copying '\0'
    addi t2, t2, 1          # i++
    j    strcpy_loop
strcpy_done:
    ret
```

<div class="highlight-box">
Copy the null terminator <strong>before</strong> branching out — otherwise the destination is not a valid C string.
</div>

---

## Calling C Library Functions from Assembly

You don't always need to reimplement string routines:

```asm
.global strlen
# ...
mv   a0, s0       # a0 = pointer to string
call strlen       # a0 = strlen(s0)
```

- Declare the symbol `.global` in your `.s` file
- Set argument registers (`a0`–`a7`) before `call`
- Save any caller-saved registers you need across the call

---

## Key Concepts Reference

| Concept | Definition |
|---------|------------|
| **Byte-addressable** | Every byte has a unique address |
| **Little-endian** | LSB at lowest address (RISC-V) |
| **Big-endian** | MSB at lowest address |
| **Two's complement** | Signed scheme; ordinary addition is correct |
| **Negate** | `invert(v) + 1`; its own inverse |
| **Sign extension** | Widen by replicating the sign bit |
| **Zero extension** | Widen by filling with 0s (unsigned) |
| **Truncation** | Narrow by keeping low bits |
| **C string** | Null-terminated byte array |
| **`lb` / `sb`** | Load/store a single byte |

---

## Summary

1. **Registers hold what the CPU computes on; RAM holds code and data.** Loads/stores cross the boundary.

2. **Memory is a byte-addressable array.** 8 bits per byte; larger values span consecutive bytes.

3. **RISC-V is little-endian.** The least significant byte is at the lowest address. Endianness matters for byte-level access and networking.

4. **Two's complement is the standard for signed integers.** One zero, MSB is sign bit, ordinary addition works for both positive and negative.

5. **Negate with `invert(v) + 1`.** Same operation converts in both directions.

6. **Sign-extend to widen; truncate to narrow.** Use `lb` (signed) vs `lbu` (unsigned) accordingly.

7. **C strings are null-terminated byte arrays.** Walk with `lb`, advance pointer by 1, stop at zero.