The Art of Image Processing - Kindle eBook Company logo

Introduction to DSP - Programming DSPs: using pointers

A naive C language program to implement an FIR filter is inefficient because it accesses array elements by array index:

y[n] = 0.0;
for (k = 0; k < N; k++)
y[n] = y[n] + c[k] * x[n-k];

To understand why accessing by array index is inefficient, remember that an array is really just a table of numbers in sequential memory locations. The C compiler only know the start address of the array. To actually read any array element the compiler first has to find the address of that particular element. So whenever an array element is accessed by its array index [i] the compiler has to make a calculation:

Finding address of array element

The diagram shows how the compiler would calculate the address of an array element specified by index as x[n - k]. The calculation requires several steps:

  • load the start address of the table in memory
  • load the value of the index n
  • load the value of the index k
  • calculate the offset [n - k]
  • add the offset to the start address of the array

This entails five operations: three reads from memory, and two arithmetic operations. Only after all five operations can the compiler actually read the array element.

C language provides the 'pointer' type precisely to avoid the inefficiencies of accessing array elements by index.

In C, the syntax *ptr indicates that ptr is a pointer which means:

  • the variable ptr is to be treated as containing an address
  • the '*' means the data is read from that address

Pointers can be modified after the data has been accessed. The syntax *ptr++ means:

  • the variable ptr is to be treated as containing an address
  • the '*' means the data is read from that address
  • the '++' means that, having read the data, the pointer ptr is incremented to point to the next sequential data element

Accessing the array elements using pointers is more efficient than by index:

Accessing arrays with pointers

Each pointer still has to be initialised: but only once, before the loop; and only to the start address of the array, so not requiring any arithmetic to calculate offsets. Within the loop, the pointers are simply incremented so that they point automatically to the next array element ready for the next pass through the loop.

Using pointers is more efficient than array indices on any processor: but it is especially efficient for DSP processors because DSP processors are excellent at address arithmetic. In fact, address increments often come for free. For example, the Lucent DSP32C processor has several 'free' modes of pointer address generation:

*rP - register indirect : read the data pointed to by the address in register rP

*rP++ - postincrement: having read the data, postincrement the address pointer to point to the next value in the array

*rP++rI - register postincrement: having read the data, postincrement the address pointer by the amount held in register rI to point to rI values further down the array

*rP++rIr - bit reversed:having read the data, postincrement the address pointer to point to the next value in the array, as if the address bits were in bit reversed order

The address increments are performed in the same instruction as the data access to which they refer: and they incur no overhead at all. More than this, as we shall see later, most DSP processors can perform two or three address increments for free in each instruction. So the use of pointers is crucially important for DSP processors.

Some C compilers optimise code. For example, one of the Texas Instruments C compilers would, with full optimisation selected, take the initial naive C code but produce assembler that corresponds closely to the code using pointers. This is very nice but there are three cautions to be observed:

  • optimisation can often be used only in restrictive circumstances - for example in the absence of interrupts
  • optimisation is compiler dependent: so code that relies on compiler optimisation could become very inefficient when ported to another compiler

One reason to use C is so that the programmer can write code that is very close to the operation of the processor. This is often desirable in DSP, where we want to have a high degree of control over exactly what the processor is doing at all times. Optimisation changes the code you wrote into code the compiler thought was better: in the worst case the code may not actually work when optimised.

backward/forward go back to start of module go back to previous page go to next page go to next module