SIMD-based Advanced Byte Scan for Start Code of H.264 and H.265



TABLE OF CONTENTS
-----------------

I. BACKGROUND
  1. Characteristic of H.264/H.265 Video Stream
    1-1) Structure of Stream in transport stream.
	1-2) Probability for zero character '0x00' to appear
  2. Byte Scan for Start Code
  3. SIMD
II. THE PROPOSED ADVANCED ALGORITHM
  1. The main idea of SIMD-based Advanced Byte Scan Algorithm
  2. SIMD-based successive zero check algorithm
III. APPENDIX
  1. Neon Register Set
  2. NEON Instruction
    2-1) VLD2.8
	2-2) VCEQ.i8
	2-3) VMOV
  3. The implemented code for SIMD-based Advanced Byte Scan

  
  

BACKGROUND
----------

1. Characteristic of H.264/H.265 Video Stream

1-1) Structure of Stream in transport stream.
h.264 and h.265 video stream consists of many nal units with '0x00 0x00 0x01' as start code:

 +----------+--------------+----------+--------------+--------+
 | 0x000001 |   nal unit   | 0x000001 |   nal unit   | ....   |
 +----------+--------------+----------+--------------+--------+
 \________________________/ \_______________________/ ...
       First NAL Unit            Second NAL Unit

Each nal unit is placed between two start codes and it consists of nal unit header and RBSPs.
Start code is one of meta data to indicate the start of a nal unit and the parser for h.264/h.265 should parse the header of nal unit which is placed after start code.

1-2) Probability for zero character '0x00' to appear
We assume that the probability for a byte character to appear is under uniform distribution.
In the case of zero character, it also follows uniform distribution because zero is one of byte characters.
In conclusion, the probability for a zero character to appear is 1/256 ( 0.39% ).



2. Byte Scan for Start Code

For the start-code based h.264/h.265 streams, it should be scanned to identify a nal unit which is placed between two nal units. The process is 'byte scanning for start code'.
In Gstreamer 1.3.2, it is implemented using Boyer-Moor heuristic algorithm.



3. SIMD
Single Instruction Multiple Data(SIMD) is a class of parallel computing. It performs the same operation on multiple data points simultaneously, which boosts the performance using data parallelism method. 
But, it has a constraint that data points should be close enough to be simultaneously accessed by SIMD cores.
Once the runtime environment satisfy the constraint, its performance can be enhanced by SIMD.

ARM NEON is one of SIMD architectures and it supports a 128-bit SIMD operations.
ARM Cortex-A series processors are equipped with NEON to accelerate multimedia and signal processing.

If you need more information, you can refer to the following:
http://en.wikipedia.org/wiki/SIMD
http://www.arm.com/products/processors/technologies/neon.php




THE PROPOSED ADVANCED ALGORITHM
-------------------------------

1. The main idea of SIMD-based Advanced Byte Scan Algorithm

Many of h.264/h.265 video streams have start-codes, which needs byte scanning to identify each nal unit. The scan function is implemented using Boyer-Moor heuristic algorithm.
The algorithm also has good performance in view of finding start code.
To improve the performance, we approach with different perspectives. We can find zero faster using neon operations.

The start codes takes up less space than other data in video streams. In addition, the probability for zero character in input stream data is only 0.39% according to BACKGROUND part.
Therefore, most of byte buffers have few start codes and the scanning function will skip most bytes of the buffer.

In conclusion, the performance relies on how fast it skips non-candidates and concentrates on candidates; because we want to find '0x00 0x00 0x01', candidate is defined as data including zero character and non-candidate is data which have no zero characters.
The problem can be split into two processes:
  a) skip non-candidates which have no start codes
  b) find a start code in candidates

The original byte scanning focuses on only 'b)'; how fast to find a start code,
whereas the proposed SIMD-based Advanced Byte Scan Algorithm dramatically boosts 'a)'; how fast to skip non-candidates. While 'b)' is already optimized and it can not be faster, 'a)' can be improved more.
If we perform 'a)' process much faster than 'b)', the overall performance is enhanced although additional process 'a)' is inserted.

In Problem 'a)',
non-candidates are byte buffers that have no start codes '0x00 0x00 0x01' or '0x00 0x00 0x00 0x01'. Also, they have no successive zero characters '0x00 0x00' because '0x00 0x00' is a subset of '0x00 0x00 0x01'.
Thus, problem 'a)' can be transformed into another problem 'c)' how fast to check if buffers include '0x00 0x00' or not.
If buffers have no successive zero characters, we don't need to scan a start code.

The proposed SIMD-based Advanced Byte Scan Algorithm is an optimized solution for problem 'c)'.
It is implemented using ARM NEON instructions and it is 4 times faster than a cpu because of 128-bit operations.
To conclude, most cases don't perform process 'b)' because it quickly classifies non-candidates and returns false before process 'b)'.



2. SIMD-based successive zero check algorithm

Even though there are many SIMD architectures, we explain the algorithm using ARM NEON instructions because the algorithm is implemented using it.

According to Section 1 in THE PROPOSED ADVANCED ALGORITHM, it tries to check if the stream include successive zero characters '0x00 0x00' or not. 
Successive zero characters start with odd index or even index. It is more expensive to exactly check which position successive zero characters exist despite using SIMD instructions.
Because the purpose of the routine is to skip non-candidates quickly, the routine must perform cheaply as possible. Therefore, we transform it into checking 0x00 on odd indices because '0x00 0x00' occupy one even index and one odd index regardless of its start position. It is a trade off.

The sequences of the algorithm:
  1) load data from memory to neon register with 'vld' operation
  2) check if each byte of the neon register is zero or not with 'vceq' operation
  3) transfer the result from neon register to arm register with 'vmov' operation

The following is examples: data0 is a non-candidate and data1 is a candidate.

check : X  O  X  O  X  O  X  O  X  O  X  O  X  O  X  O  X  O  X  O  X  O  X  O  X  O  X  O  X  O  X  O
offset: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
data0 :|01|02|03|04|05|06|07|08|09|0a|0b|0c|0d|0e|0f|10|11|12|13|14|15|16|17|18|19|1a|1b|1c|1d|1e|1f|20|
data1 :|75|cb|00|b9|4e|71|f4|c5|41|ad|d1|35|64|92|d8|b3|bb|6c|00|00|01|73|08|d7|f2|0a|23|4a|f8|8f|87|c7|
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

	   
Case1) data0 is a non-candidate
According to the above sequence of the algorithm, because neon processor has its own registers, data0[0:31] is loaded from memory to neon register d16 to d19; D register is a 64-bit register. 
There exist lots of types for neon load operations. In this case, we use interleaved byte load with offset 2, which means load even indexed data to first two registers and load odd indexed data to second two registers as follows.

offset: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
q8    :|01|03|05|07|09|0b|0d|0f|11|13|15|17|19|1b|1d|1f|
q9    :|02|04|06|08|0a|0c|0e|10|12|14|16|18|1a|1c|1e|20|
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

After loading, it compares odd indexed data(q9) with zero as follows.

offset: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
q9    :|02|04|06|08|0a|0c|0e|10|12|14|16|18|1a|1c|1e|20|
#0    :|00|00|00|00|00|00|00|00|00|00|00|00|00|00|00|00|
result:|00|00|00|00|00|00|00|00|00|00|00|00|00|00|00|00|
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

After that, the result which is placed on neon register q9 is transferred to two arm registers to control the scanning window by the result. In this case, the result have all zero bits which means there are no zero byte on original stream. Therefore, it just skips the loaded 32 bytes because it is a non-candidate.


Case2) data1 is a candidate
The sequence is almost same with Case1)'s. 
Using interleaved byte load operations, it loads data from memory into neon registers and compares each element with zero as follows.

offset: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
q8    :|75|00|4e|f4|41|d1|64|d8|bb|00|01|08|f2|23|f8|87|
q9    :|cb|b9|71|c5|ad|35|92|b3|6c|00|73|d7|0a|4a|8f|c7|
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

offset: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
q9    :|cb|b9|71|c5|ad|35|92|b3|6c|00|73|d7|0a|4a|8f|c7|
#0    :|00|00|00|00|00|00|00|00|00|00|00|00|00|00|00|00|
result:|00|00|00|00|00|00|00|00|00|11|00|00|00|00|00|00|
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

The result are transferred to 4 arm registers and it checks if the result is zero or not to skip it.
Even if first 8-byte integer is zero, last 8-byte integer is non-zero. Thus, it skips first 16 bytes data and scans start code on last 16 bytes data. Because scanning routine is the same with original gstreamer code, we do not miss the start code.




APPENDIX
--------

1. Neon Register Set
The NEON D registers and Q registers share the space and each of the Q0-Q15 registers map onto a pair of D registers as follows. Software does not have to explicitly switch between them.

   64-bit   64-bit                           128-bit
+---------+---------+ - - - - - - - - +-------------------+
|   d0    |   d1    |                 |        q0         |
+---------+---------+ - - - - - - - - +-------------------+
|   d2    |   d3    |                 |        q1         |
+---------+---------+ - - - - - - - - +-------------------+
|   d4    |   d5    |                 |        q2         |
+---------+---------+ - - - - - - - - +-------------------+
|   ...   |   ...   |                 |        ...        |
+---------+---------+ - - - - - - - - +-------------------+
|   d28   |   d29   |                 |        q14        |
+---------+---------+ - - - - - - - - +-------------------+
|   d30   |   d31   |                 |        q15        |
+---------+---------+ - - - - - - - - +-------------------+



2. NEON Instruction
2-1) VLD2.8 

    Interleave pattern(1,2,3 or 4)--\        /-- NEON register list
                                  VLD2.8 {d0,d1}, [r0]
       Load(VLD) or store(VST)----/     \           \-- Address in ARM register
	                                     \-- Element type(8, 16 or 32)

VLD instruction is to load data from memory to neon registers and it has some options: interleave pattern and element type;
 - interleave pattern: the gap between corresponding elements in each structure
 - element type: the number of bits in the accessed elements

The above example loads data from memory which r0 indicates to d0 and d1; d0 and d1 are placed on q0
Because it has two as interleave pattern and eight as element type, it loads 8-bit data, deinterleaving even and odd elements into d0(even) and d1(odd) registers.
The options are very useful for multimedia data such as RGB or ARGB image.

If you need more information, you can refer to http://community.arm.com/groups/processors/blog/2010/03/17/coding-for-neon--part-1-load-and-stores


2-2) VCEQ.i8

    Equal(EQ), Greater than or Equal(GE), Grater Than(GT), Less than or Equal(LE), and Less Than(LT)
	                               \
	                                \      /-- destination neon register
                                  VCEQ.i8 q9, q9, #0
                                        \      \   \-- source neon register1 or #0 (zero)
										 \      \-- source neon register0
										  \-- element data type (i8, i16, i32, f32, ...)

VCEQ is a sort of vector compare operations; VCEQ, VCGE, VCGT, VCLE, and VCLT
VCEQ takes the value of each element in a vector, and compares it with the value of the corresponding element of a second vector or zero. If the condition is true, the corresponding element in the destination vector is set to all ones. Otherwise, it is set to all zeros. Element data type indicates the data type and size of each element; i8 is 8-bit integer.

The above example compares q9 register with zero. After that, the result is stored on q9.

2-3) VMOV

           destination arm register0 --\    /-- destination arm register1
                                  VMOV r0, r1, d0
					    source neon register --/

VMOV is to transfer contents between two ARM registers and a 64-bit extension register. and it is for sharing between neon coprocessor and arm processor.

The above example transfers the contents of the low half of d0 into r0, and the contents of the high half of d0 into r1.



3. The implemented code for SIMD-based Advanced Byte Scan
+------------------------------------------------------------------------------+
| asm volatile (                                                               |
|     "vld2.8  {d16-d19}, [%[PDATA]]     \n"                                   |
|     "vceq.i8 q9, q9, #0                \n"                                   |
|     "vmov  %Q[RESULT0], %H[RESULT0], d18 \n"                                 |
|     "vmov  %Q[RESULT1], %H[RESULT1], d19 \n"                                 |
|     :[RESULT0] "=r" (zero_check_map_0),[RESULT1] "=r" (zero_check_map_1)     |
|     :[PDATA] "r" (pdata)                                                     |
|     :"d16", "d17", "d18", "d19", "q9");                                      |
|                                                                              |
| if (zero_check_map_0 == 0) {                                                 |
|   if (zero_check_map_1 == 0) {                                               |
|     pdata += 32;                                                             |
|     continue;                                                                |
|   }                                                                          |
|                                                                              |
|   pdata += 16;                                                               |
| }                                                                            |
+------------------------------------------------------------------------------+








