Assembly

The NDK allows you to use C and C++ in your Android applications. Chapter 2 showed you what native code would look like after the C or C++ code is compiled and how you could use objdump –d to disassemble a file (object file or library). For example, the ARM assembly code of computeIterativelyFaster is shown again in Listing 3–1.

In addition to allowing you to use C or C++ in your application, the Android NDK also lets you to write assembly code directly. Strictly speaking, such a feature is not NDK-specific as assembly code is supported by the GCC compiler, which is used by the Android NDK. Consequently, almost everything you learn in this chapter can also be applied to other projects of yours, for example in applications targeting iOS devices like the iPhone.

As you can see, assembly code can be quite difficult to read, let alone write. However, being able to understand assembly code will allow you to more easily identify bottlenecks and therefore more easily optimize your applications. It will also give you bragging rights.

To familiarize yourself with assembly, we will look at three simple examples:

• Computation of the greatest common divisor
• Conversion from one color format to another
• Parallel computation of average of 8-bit values

These examples are simple enough to understand for developers who are new to assembly, yet they exhibit important principles of assembly optimization. Because these examples introduce you to only a subset of the available instructions, a more complete introduction to the ARM instruction set will follow as well as a brief introduction to the überpowerful ARM SIMD instructions. Finally, you will learn how to dynamically check what CPU features are available, a mandatory step in your applications that target features not available on all devices.

Greatest Common Divisor

The greatest common divisor (gcd) of two non-zero integers is the largest positive integer that divides both numbers. For example, the greatest common divisor of 10 and 55 is 5. An implementation of a function that computes the greatest common divisor of two integers is shown in Listing 3–2.

If you define APP_ABI in your Application.mk file such that x86, armeabi, and armeabi-v7 architectures are supported in your application, then you will have three different libraries. Disassembling each library will result in three different pieces of assembly code. However, since you have the option to compile in either ARM or Thumb mode with the armeabi and armeabi-v7a ABIs, there are actually a total of five pieces of code you can review.

Listing 3–3 shows the resulting ×86 assembly code while Listing 3–4 and Listing 3–5 show the ARMv5 and ARMv7 assembly code respectively. Because different versions of compilers can output different code, the code you will observe may be slightly different than the that shown here. The generated code will also depend on the optimization level and other options you may have defined.

If you are familiar with the x86 mnemonics, you can see that this code makes heavy use of the jump instructions (jne, jmp, je, jb). Also, while most instructions are 16-bit (for example, “f3 c3”), some are 32-bit.

As it turns out, the GCC compiler generates the same code for the armeabi and armeabi-v7a ABIs when the code shown in Listing 3–2 is compiled in ARM mode. This won't always be the case though as the compiler usually takes advantage of new instructions defined in newer ABIs.

Because you could decide to compile the code in Thumb mode instead of ARM mode, let's also review the code that would be generated in Thumb mode. Listing 3–6 shows the ARMv5 assembly code (armeabi ABI in Application.mk) while Listing 3–7 shows the ARMv7 assembly code (armeabi-v7a ABI in Application.mk).

All instructions in Listing 3–6 are 16-bit (that is, “e7f4,” the last instruction of the listing) and the twelve instructions therefore require 24 bytes of space.

This time, the two listings are different. While the ARMv5 architecture uses the Thumb instruction set (all 16-bit instructions), the ARMv7 architecture supports the Thumb2 instruction set and instructions can be 16- or 32-bit.

As a matter of fact, Listing 3–7 looks a lot like Listing 3–5. The main difference is with the use of the ite (if-then-else) instruction in Listing 3–7, and the fact that the ARM code is 40-byte long while the Thumb2 code is only 28-byte long.

Usually, the GCC compiler does a pretty good job and you won't have to worry too much about the generated code. However, if a piece of code you wrote in C or C++ turns out to be one of the bottlenecks of your application, you should carefully review the assembly code the compiler generated and determine whether you could do better by writing the assembly code yourself. Very often the compiler will generate high-quality code and you won't be able to do better. That being said, there are cases where, armed with both an intimate knowledge of the instruction set and a slight taste for suffering, you can achieve better results than the compiler.

The gcd function can indeed be implemented differently, resulting in code not only faster but also more compact, as shown in Listing 3–8.

Not including the final instruction to return from the function, the core of the algorithm is implemented in only four instructions. Measurements also showed this implementation as being faster. Note the single call to the CMP instruction in Listing 3–8 compared with the two calls in Listing 3–7.

This code can be copied in a file called gcd_asm.S and added to the list of files to compile in Android.mk. Because this file is using ARM instructions, it obviously won't compile if the target ABI is x86. Consequently, your Android.mk file should make sure the file is only part of the list of files to compile when it is compatible with the ABI. Listing 3–9 shows how to modify Android.mk accordingly.

Because gcd_asm.S is already written using assembly code, the resulting object file should look extremely similar to the source file. Listing 3–10 shows the disassembled code and indeed, the disassembled code is virtually identical to the source.

By simplifying the assembly code, we achieved better results without dramatically making maintenance more complicated.

Color Conversion

A common operation in graphics routines is to convert a color from one format to another. For example, a 32-bit value representing a color with four 8-bit channels (alpha, red, green, and blue) could be converted to a 16-bit value representing a color with three channels (5 bits for red, 6 bits for green, 5 bits for blue, no alpha). The two formats would typically be referred to as ARGB8888 and RGB565 respectively.

Listing 3–11 shows a trivial implementation of such a conversion.

Once again, five pieces of assembly code can be analyzed. Listing 3–12 shows the x86 assembly code, Listing 3–13 shows the ARMv5 assembly code in ARM mode, Listing 3–14 shows the ARMv7 assembly code in ARM mode, Listing 3–15 shows the ARMv5 assembly code in Thumb mode, and finally Listing 3–16 shows the ARMv7 assembly code in Thumb mode.

Simply looking at how many instructions are generated, the ARMv5 code in Thumb mode seems to be the least efficient. That being said, counting the number of instructions is not an accurate way of determining how fast or how slow a piece of code is going to be. To get a closer estimate of the duration, one would have to count how many cycles each instruction will need to complete. For example, the “orr r3, r2” instruction needs only one cycle to execute. Today's CPUs make it quite hard to compute how many cycles will ultimately be needed as they can execute several instructions per cycle and in some cases even execute instructions out of order to maximize throughput.

Now, it is possible to write a slightly different version of the same conversion function using the UBFX and BFI instructions, as shown in Listing 3–17.

Since this code uses the UBFX and BFI instructions (both introduced in the ARMv6T2 architecture), it won't compile for the armeabi ABI (ARMv5). Obviously it won't compile for the x86 ABI either.

Similar to what was shown in Listing 3–9, your Android.mk should make sure the file is only compiled with the right ABI. Listing 3–18 shows the addition of the rgb.c and rgb_asm.S files to the build.

If you add rgb_asm.S to the list of files to compile with the armeabi ABI, you will then get the following errors:

Error: selected processor does not support `ubfx r1,r0,#3,#5'

Error: selected processor does not support `bfi r1,r0,#5,#6'

Error: selected processor does not support `bfi r1,r0,#11,#5'

Parallel Computation of Average

In this example, we want to treat each 32-bit value as four independent 8-bit values and compute the byte-wise average between two such values. For example, the average of 0×10FF3040 and 0×50FF7000 would be 0×30FF5020 (average of 0×10 and 0×50 is 0×30, average of 0×FF and 0×FF is 0×FF).

An implementation of such function is shown in Listing 3–19.

Like with the two previous examples, five pieces of assembly code are shown in Listings 3–20 to 3–24.

Because the ARMv5 MOV instruction cannot simply copy the value to the register, an LDR instruction is used instead to copy 0×01010101 to register r3. Similarly, an LDR instruction is used to copy 0×7f7f7f7f to r2.

Instead of using an LDR instruction to copy 0x01010101 to r3, the ARMv7 code uses two MOV instructions: the first one, MOVW, is to copy a 16-bit value (0x0101) to the bottom 16 bits of r3 while the second one, MOVT, is to copy 0×0101 to the top 16 bits of r3. After these two instructions, r3 will indeed contain the 0×01010101 value. The rest of the assembly code looks like the ARMv5 assembly code.

Since this code makes use of the r4 register, it needs to be saved onto the stack and later restored

The Thumb2 assembly code is more compact as only one instruction is needed to copy 0×01010101 and 0×7f7f7f7f to r3 and r0.

Before deciding to write optimized assembly code, you may stop and think a little bit about how the C code itself could be optimized. After a little bit of thinking, you may end up with the code shown in Listing 3–25.

The C code is more compact that the first version and would appear to be faster. The first version used two >>, four &, and two + operations (total of eight “basic” operations) while the new version uses only five “basic” operations. Intuitively, the second implementation should be faster. And it is indeed.

Listing 3–26 shows the ARMv7 Thumb resulting assembly code.

This faster implementation results in faster and more compact code (not including the instruction to return from the function, four instructions instead of eight).

While this may sound terrific, a closer look at the ARM instruction set reveals the UHADD8 instruction, which would perform an unsigned byte-wise addition, halving the results. This happens to be exactly what we want to compute. Consequently, an even faster implementation can easily be implemented and is shown in Listing 3–27.

Other “parallel instructions” exist. For example, UHADD16 would be like UHADD8 but instead of performing byte-wise additions it would perform halfword-wise additions. These instructions can improve performance significantly but because compilers have a hard time generating code that uses them, you will often find yourself having to write the assembly code manually in order to take advantage of them.

Writing whole functions using assembly code can quickly become tedious. In many cases, only parts of a routine would benefit from using assembly code while the rest can be written in C or C++. The GCC compiler lets you mix assembly with C/C++, as shown in Listing 3–28.

The updated Android.mk is shown in Listing 3–29.

This example shows that sometimes, good knowledge of the instruction set is needed to achieve the best performance. Since Android devices are mostly based on ARM architectures, you should focus your attention on the ARM instruction set. The ARM documentation available on the ARM website (infocenter.arm.com) is of great quality so make sure you use it.

ARM Instructions

ARM instructions are plentiful. While the goal is not to document in great detail what each one does, Table 3-1 shows the list of available ARM instructions, each one with a brief description.

As you become familiar with them, you will learn that some of them are used much more often than others, albeit the more obscure ones are often the ones that can dramatically improve performance. For example, the ADD and MOV are practically ubiquitous while the SETEND instruction is not going to be used very often (yet it is a great instruction when you need to access data of different endianness).

ARM NEON

NEON is a 128-bit SIMD (Single Instruction, Multiple Data) extension to the Cortex A family of processors. If you understood what the UHADD8 instruction was doing in Listing 3–27, then you will easily understand NEON.

NEON registers are seen as vectors. For example, a 128-bit NEON register can be seen as four 32-bit integers, eight 16-bit integers, or even sixteen 8-bit integers (the same way the UHADD8 instruction interprets a 32-bit register as four 8-bit values). A NEON instruction would then perform the same operation on all elements.

NEON has several important features:

• Single instruction can perform multiple operations (after all, this is the essence of SIMD instructions)
• Independent registers
• Independent pipeline

Many NEON instructions will look similar to ARM instructions. For example, the VADD instruction will add corresponding elements in two vectors, which is similar to what the ADD instruction does (although the ADD instruction simply adds two 32-bit registers and does not treat them as vectors). All NEON instructions start with the letter V, so identifying them is easy.

There are basically two ways to use NEON in your code:

• You can use NEON instructions in hand-written assembly code.
• You can use NEON intrinsics defined in arm-neon.h, a header file provided in the NDK.

The NDK provides sample code for NEON (hello-neon), so you should first review this code. While using NEON can greatly increase performance, it may also require you to modify your algorithms a bit to fully take advantage of vectorization.

To use NEON instructions, make sure you add the .neon suffix to the file name in Android.mk's LOCAL_SRC_FILES. If all files need to be compiled with NEON support, you can set LOCAL_ARM_NEON to true in Android.mk.

A great way to learn about NEON is to look at the Android source code itself. For example, SkBlitRow_opts_arm.cpp (in the external/skia/src/opts directory) contains several routines using NEON instructions, using asm() or intrinsics. In the same directory you will also find SkBlitRow_opts_SSE2.cpp, which contains optimized routines using ×86 SIMD instructions. The Skia source code is also available online at http://code.google.com/p/skia.

CPU Features

As you have seen already, not all CPUs are the same. Even within the same family of processors (for example, ARM Cortex family), not all processors support the same features as some are optional. For example, not all ARMv7 processors support the NEON extension or the VFP extension. For this reason, Android provides functions to help you query what kind of platform the code is running on. These functions are defined in cpu-features.h, a header file provided in the NDK, and Listing 3–30 shows you how to use these functions to determine whether a generic function should be used or one that takes advantage of the NEON instruction set.

To use the CPU features functions, you will have to do two things in your Android.mk:

• Add “cpufeatures” to the list of static libraries to link with (LOCAL_STATIC_LIBRARIES :=cpufeatures).
• Import the android/cpufeatures module by adding $(call import-module,android/cpufeatures) at the end of Android.mk.

Typically, probing the capabilities of the platform will be one of the first tasks you will have to perform in order to use the best possible functions.

If your code depends on the presence of the VFP extension, you may have to check also whether NEON is supported. The ANDROID_CPU_ARM_FEATURE_VFPv3 flag is for the minimum profile of the extension with sixteen 64-bit floating-point registers (D0 to D15). If NEON is supported, then thirty-two 64-bit floating-point registers are available (D0 to D31). Registers are shared between NEON and VFP and registers are aliased:

• Q0 (128-bit) is an alias for D0 and D1 (both 64-bit).
• D0 is an alias for S0 and S1 (S registers are single-precision 32-bit registers).

The fact that registers are shared and aliased is a very important detail, so make sure you use registers carefully when hand-writing assembly code.