Byte, halfword, and word access in ARM Architecture - Time & Space Complexity

Time Complexity: Byte, halfword, and word access

O(n)

Understanding Time Complexity

When working with ARM assembly, accessing data in bytes, halfwords, or words affects how many steps the processor takes.

We want to understand how the time to access memory changes with the size of data units.

Scenario Under Consideration

Analyze the time complexity of the following ARM code snippet accessing different data sizes.

    LDRB R0, [R1]      // Load byte
    LDRH R2, [R1, #2]  // Load halfword
    LDR  R3, [R1, #4]  // Load word
    

This code loads a byte, a halfword (2 bytes), and a word (4 bytes) from memory addresses based on R1.

Identify Repeating Operations

Look at the memory access instructions and how often they repeat if in a loop.

• Primary operation: Memory load instructions (LDRB, LDRH, LDR)
• How many times: Each instruction runs once here, but if repeated in a loop, each access repeats per iteration.

How Execution Grows With Input

If we access n data units, each load instruction runs n times.

Input Size (n)	Approx. Operations
10	10 loads
100	100 loads
1000	1000 loads

Pattern observation: The number of load operations grows directly with the number of data units accessed.

Final Time Complexity

Time Complexity: O(n)

This means the time to access data grows linearly as the number of bytes, halfwords, or words increases.

Common Mistake

[X] Wrong: "Accessing a byte is always faster than accessing a word by a big margin."

[OK] Correct: While bytes are smaller, the processor often reads full words internally, so byte access may take similar time as word access.

Interview Connect

Understanding how data size affects memory access time helps you reason about performance in low-level programming and embedded systems.

Self-Check

"What if we changed from sequential byte accesses to accessing only every fourth byte (word-aligned)? How would the time complexity change?"

Practice

1. What size of data does a halfword represent in ARM architecture?

easy

A. 64 bits

B. 8 bits

C. 32 bits

D. 16 bits

Solution

1. Step 1: Understand data size terms in ARM

   In ARM, a byte is 8 bits, a halfword is twice that size, and a word is 32 bits.

2. Step 2: Identify halfword size

   A halfword is 16 bits because it is two bytes (2 x 8 bits = 16 bits).

3. Final Answer:

   16 bits -> Option D

4. Quick Check:

   Halfword = 16 bits [OK]

Hint: Halfword always means 16 bits or 2 bytes [OK]

Common Mistakes:

• Confusing halfword with byte size
• Thinking halfword is 32 bits
• Mixing halfword with word size

2. Which of the following is the correct ARM instruction syntax to load a single byte from memory into a register?

easy

A. STRB R0, [R1]

B. LDRH R0, [R1]

C. LDRB R0, [R1]

D. LDR R0, [R1]

Solution

1. Step 1: Identify load instructions for different sizes

   In ARM, LDRB loads a byte, LDRH loads a halfword, and LDR loads a word.

2. Step 2: Choose instruction for loading a byte

   LDRB R0, [R1] loads a byte from memory address in R1 into R0.

3. Final Answer:

   LDRB R0, [R1] -> Option C

4. Quick Check:

   LDRB = Load Byte [OK]

Hint: LDRB means load byte, LDRH halfword, LDR word [OK]

Common Mistakes:

• Using LDR instead of LDRB for byte load
• Confusing STRB (store) with load instructions
• Using LDRH which loads 16 bits, not 8

3. Consider the following ARM assembly code snippet:

LDR R0, [R1]
LDRH R2, [R1, #2]
LDRB R3, [R1, #1]

If R1 points to memory starting with bytes 0x12 0x34 0x56 0x78, what will be the value loaded into R2?

medium

A. 0x3456

B. 0x5678

C. 0x7856

D. 0x5634

Solution

1. Step 1: Understand memory layout and addressing

   Memory bytes at R1: 0x12 (offset 0), 0x34 (offset 1), 0x56 (offset 2), 0x78 (offset 3). ARM is little-endian, so lower address holds least significant byte.

2. Step 2: Calculate halfword loaded at offset #2

   Halfword at offset 2 includes bytes at offsets 2 and 3: 0x56 (LSB), 0x78 (MSB). So value is 0x5678.

3. Final Answer:

   0x5678 -> Option B

4. Quick Check:

   Halfword at offset 2 = 0x5678 [OK]

Hint: Remember little-endian: lower address = least significant byte [OK]

Common Mistakes:

• Reading bytes in wrong order (big-endian)
• Using wrong offset for halfword
• Confusing byte and halfword sizes

4. An ARM program tries to load a halfword from an odd memory address using LDRH R0, [R1]. What is the likely problem?

medium

A. Alignment fault or unpredictable behavior

B. It will load a full word instead

C. It will automatically adjust to next even address

D. No problem, halfword loads from any address

Solution

1. Step 1: Understand alignment requirements in ARM

   Halfword accesses must be aligned to even addresses (multiples of 2). Loading from odd addresses causes alignment faults or unpredictable results.

2. Step 2: Identify behavior on misaligned halfword load

   ARM architecture typically raises an alignment fault or behaves unpredictably if halfword is loaded from an odd address.

3. Final Answer:

   Alignment fault or unpredictable behavior -> Option A

4. Quick Check:

   Halfword must be even address [OK]

Hint: Halfword loads require even addresses; odd causes faults [OK]

Common Mistakes:

• Assuming automatic address adjustment
• Thinking halfword loads from any address are safe
• Confusing halfword with byte alignment

5. You need to copy a 32-bit word from an unaligned address in memory to a register in ARM. Which approach correctly handles this situation?

hard

A. Use four byte loads (LDRB) and combine them manually in the register

B. Use a single LDR instruction directly on the unaligned address

C. Use LDRH twice and combine two halfwords

D. Use STR instruction to store the word first, then load it

Solution

1. Step 1: Understand alignment restrictions for word loads

   ARM requires word (32-bit) loads to be aligned to 4-byte boundaries. Unaligned word loads cause faults or incorrect data.

2. Step 2: Choose method to safely load unaligned word

   Loading four bytes individually with LDRB and combining them in the register avoids alignment faults and correctly reconstructs the word.

3. Final Answer:

   Use four byte loads (LDRB) and combine them manually in the register -> Option A

4. Quick Check:

   Unaligned word load = combine bytes manually [OK]

Hint: Unaligned word? Load bytes separately and combine [OK]

Common Mistakes:

• Using single LDR on unaligned address causing faults
• Assuming LDRH twice works for unaligned word
• Misusing STR which stores, not loads