Vector table structure in ARM Architecture - Time & Space Complexity

Time Complexity: Vector table structure

O(1)

Understanding Time Complexity

We want to understand how the time to access an interrupt handler grows as the number of interrupts increases in a vector table.

How does the structure of the vector table affect the speed of finding the right handler?

Scenario Under Consideration

Analyze the time complexity of the following vector table lookup code.

    LDR R0, =VectorTable  ; Load base address of vector table
    LDR R1, [R0, R2, LSL #2] ; Load handler address using interrupt number in R2
    BX R1                 ; Branch to handler
    

This code loads the address of the interrupt handler directly from the vector table using the interrupt number as an index.

Identify Repeating Operations

In this code, there is no loop or recursion.

• Primary operation: Single memory load using the interrupt number as index.
• How many times: Exactly once per interrupt.

How Execution Grows With Input

The time to find the handler does not increase as the number of interrupts grows.

Input Size (n)	Approx. Operations
10	1 memory load
100	1 memory load
1000	1 memory load

Pattern observation: The operation count stays the same no matter how many interrupts there are.

Final Time Complexity

Time Complexity: O(1)

This means the time to find the interrupt handler is constant and does not depend on the number of interrupts.

Common Mistake

[X] Wrong: "Finding the interrupt handler takes longer if there are more interrupts in the vector table."

[OK] Correct: The vector table uses direct indexing, so the handler address is found immediately without searching through entries.

Interview Connect

Understanding how direct indexing in a vector table leads to constant time access is a useful skill for embedded systems and low-level programming roles.

Self-Check

"What if the vector table was implemented as a linked list instead of an array? How would the time complexity change?"

Practice

1. What is the first entry in the ARM vector table?

easy

A. Program counter start address

B. Reset handler address

C. Initial stack pointer address

D. Interrupt service routine address

Solution

1. Step 1: Understand vector table structure

   The ARM vector table begins with the initial stack pointer value to set up the stack.

2. Step 2: Identify the first entry

   The first entry is the initial stack pointer address, followed by the reset handler address.

3. Final Answer:

   Initial stack pointer address -> Option C

4. Quick Check:

   First entry = Initial stack pointer address [OK]

Hint: Remember: stack pointer comes before reset handler [OK]

Common Mistakes:

• Confusing reset handler as first entry
• Thinking program counter is first
• Assuming interrupt routine is first

2. Which of the following correctly describes the second entry in the ARM vector table?

easy

A. Reset handler address

B. Initial stack pointer address

C. Undefined instruction handler

D. Non-maskable interrupt handler

Solution

1. Step 1: Recall vector table order

   The first entry is the initial stack pointer, so the second entry is the reset handler.

2. Step 2: Confirm second entry role

   The reset handler is the address where the processor starts executing after reset.

3. Final Answer:

   Reset handler address -> Option A

4. Quick Check:

   Second entry = Reset handler address [OK]

Hint: Second entry always points to reset handler [OK]

Common Mistakes:

• Mixing up with interrupt handlers
• Choosing stack pointer again
• Confusing with exception handlers

3. Given the following vector table snippet:

0x00000000: 0x20001000  (Initial SP)
0x00000004: 0x00001005  (Reset Handler)
0x00000008: 0x00001010  (NMI Handler)
0x0000000C: 0x00001020  (HardFault Handler)

Which address will the processor jump to on a HardFault exception?

medium

A. 0x20001000

B. 0x00001005

C. 0x00001010

D. 0x00001020

Solution

1. Step 1: Locate HardFault entry in vector table

   The HardFault handler address is at offset 0x0C in the vector table.

2. Step 2: Identify the address at 0x0000000C

   The address at 0x0000000C is 0x00001020, which is the HardFault handler.

3. Final Answer:

   0x00001020 -> Option D

4. Quick Check:

   HardFault handler = 0x00001020 [OK]

Hint: Match exception to its vector table offset [OK]

Common Mistakes:

• Choosing reset handler address
• Confusing NMI and HardFault handlers
• Selecting initial stack pointer

4. A developer sets the vector table's first entry to 0x00000000 instead of the initial stack pointer. What issue will most likely occur?

medium

A. Stack pointer will be invalid causing a crash

B. Processor will reset normally

C. Reset handler will not execute

D. Interrupts will be ignored

Solution

1. Step 1: Understand role of first vector entry

   The first entry sets the initial stack pointer address for the processor.

2. Step 2: Analyze effect of setting it to zero

   Setting it to 0x00000000 means the stack pointer points to an invalid memory location, causing a crash.

3. Final Answer:

   Stack pointer will be invalid causing a crash -> Option A

4. Quick Check:

   Invalid stack pointer = Crash [OK]

Hint: First vector must be valid stack pointer [OK]

Common Mistakes:

• Thinking reset handler won't run
• Assuming interrupts are disabled
• Believing processor resets normally

5. You want to add a custom interrupt handler for a new peripheral. Where in the ARM vector table should you place this handler's address?

hard

A. At the first entry replacing the initial stack pointer

B. At the specific interrupt vector slot assigned to that peripheral

C. At the second entry replacing the reset handler

D. At the end of the vector table after all default handlers

Solution

1. Step 1: Understand vector table layout

   The vector table has fixed slots for each exception and interrupt type.

2. Step 2: Identify correct slot for custom interrupt

   Custom peripheral interrupts must be placed at their assigned interrupt vector slot, not at stack pointer or reset handler entries.

3. Final Answer:

   At the specific interrupt vector slot assigned to that peripheral -> Option B

4. Quick Check:

   Custom handler = Assigned interrupt vector slot [OK]

Hint: Place handlers in their assigned vector slots only [OK]

Common Mistakes:

• Replacing stack pointer or reset handler
• Appending handler at vector table end
• Ignoring fixed vector slot assignments