Board Support Package

* Two Steps
- Basic init
1) Disable interrupts and cache
2) Init memory controller and cache
3) Init stack register and other registers
4) Init URAT for debugging
This step generally uses Assembly to implement the above tasks
- Board init
1) Clear memory
2) Init interrupts
3) Init timers
4) Init other hardwares
5) Init RTOS
This step would run C codes

Fixed Point Arithmetic in DSP

* Rules for Fixed-Point Arithmetic
- Unsigned wordlength: U(a, b) is a + b
Range: [0, 2**a - 2**(-b)]
- Signed wordlength: A(a, b) is a + b + 1(sign)
Range: [-2**a, 2**a - 2**(-b)]
- Addition
Scale must be the same for all the operands
X(e, f) + Y(e, f) = Z(e+1, f)
- Multiplication
X(a, b) * Y(e, f) = Z(a+e, b+f) Note: exclude the sign bit
- Shifting to divide/multiple by a power of two, or to change the scaling
1) multiply/divide by a power of two: X(a, b) >> n = X(a, b)
where if n greater than zero, right shift and if n less than zero, left shift
2) modifying scale: X(a, b) >> n = X(a+n, b-n)
Note these operations might result in a loss of precision or overflow.

* How to scale
- For A(a, b) scale, the fixed point num would be X = (x + 2**(-b-1)) * 2**b
- Round is better than truncation for scaling in terms of error. Always add 2**(b-1) when scaling to b
- The maximal value of output for FIR
Ymax = Xmax * sum(abs(bi)) where bi is the coefficients of FIR. So sum(abs(bi)) is generally one.
- Scale the coefficients for FIR
For signed number with M bit wordlength, in order to represent the maximal value of the coefficients, S1 = floor(log2(2**(M-1)-1)/max(abs(bi)))
In order to make the final sum not overflow, S2 = A - L - ceiling(log2(sum(abs(bi)))), where A is the length of accumulator, L is the bitwidth of inputs.
So the final scale for the coefficients of FIR should be S = min(S1, S2)

Difference Between JPEG and MPEG

- JPEG deals with luma and chroma with different Q table and VLC table. MPEG does Q and VLE independent of luma and chroma.
- JPEG does not standardize these tables the customized table could be transmitted within the stream while MPEG does esp. VLC table is not allowed to be changed by user.
- For VLC, both JPEG and MPEG deal with DC(intra-MB), AC(intra-MB) differently. Meanwhile the VLC structure is different too. For JPEG, (run, size) is coded with VLC while level is coded with minimal bits and the sign could be derived from level code and size. MPEG just does the same thing but combining these triple together with different VLC table and the sign is coded explicitly. The code length would be LUTed by the prefix of each code. They are not compatible with each other.
- MPEG-2 has more precision for DC component: 8-11 bits while JPEG only supports 8 bits. like MPEG-1.
- The syntax elements above slice should be fixed (in general) or variable length coded in MPEG. The elements within and below slice should be variable length coded, esp. in the MB level everything is VLEed, like MV diff, CBP, QP diff, etc.

Random Number Generation

* BigRand and RandInt
long long bigrand()
{ return (long long)RAND_MAX * rand() + rand(); }
int randint(int l, int u)
{ return l + bigrand() % (u-l+1); }
Here rand() returns one random number with 32bits; bigrand returns one big random number with 64bits and randint(l, u) returns one random number between l and u.

* Select K random numbers in an array of N with sorted output
To select s number out of r remaining, the next number would be selected with probability s/r. It could be expressed by
if (bigrand() % r) < s
The pseudocode is:
select = K
remaining = N
for i = [0, N-1]
   if (bigrand() % remaining) < select
     print i
     select--
   remaining--
Alternatively, the data structure of set could be used:
initialize set S to empty
size = 0
while size < K do
   t = bigrand() % N
   if t is not in S
     insert t into S
     size++
print S in sorted order
The third one allowing number repeating is to shuffle the array, like this:
for i = [0, N-1]
   swap(i, randint(i, n-1))

Searching

* Sequential Search O(N)

* Binary Search O(logN)

* Hashing O(1)

* Binary Search Tree O(logN)

* Key Index to Array O(1)
Note its different space requirement from that of hashing

* Examples
- Find the missing/duplicate element in one unsorted array
Binary search for large array. In some cases, it could be solved by calculating the difference between the sum of the array and the sum of the range of number.
- Find all sets of angrams in one dictionary
Set a key for each word, then sort by the key to group them.
- Find the angrams of one word in one dictionary
After finish Q2, use binary search to do it.
- Find the Kth largest number in one non-repeated array
Order statistics
- Find the median of two sorted arrays
- Find one number which duplicates more than half size of one array
- Bitmap sort actually uses key index

Sorting

* Selection Sort
Find the smallest one and put it in the leftest slot, then find the second smallest one and put it in the second slot, and so on. The average and worst case are O(N^2).

* Insertion Sort
Compare new element with the sorted list in its left. The worst case is O(N^2) and generally it is used for almost sorted array with O(N). It is stable.

* Heapsort
In place sort without recursion and the worst case is O(NlogN).

* Merge Sort
Divide and conquer. The worst case is O(NlogN) with O(N) space. It is very useful for sorting data on disk that is too large to fit entirely into primary memory.

* Quick Sort
Partition and recursion. The average case is O(NlogN) with O(logN) space.

* Bitmap Sort
The data in one specific range with limited duplication. O(N)

* Binary Search Tree
If the size of the array is not known in advance, the binary search tree could be used to do the sorting. Heap could be used too. However, it might be harder to implement heap with list than with array.

* Examples
- Sort a file containing at most n(10^7) positive integers, each less than n without duplication. The main memory to be used is limited to one megabyte.
Merge sort, quick sort with multiple passes, and bitmap sort (with multiple passes)
- What if the number in Q1 might occur at most ten times or each non-repeated number is associated with one of three prefix: 800, 877 and 880?
- Transpose one 4000X4000 matrix
Apply (row, col) for each element and stable sort (insertion sort) by row then by col.

Bit Operation

* Bit Operations
~, &, |, ^, << and >>.

* Examples
- Check whether the system is big endian or little endian
Why does this solution not work?
int i = 1;
char c = (char)i; /* c == 1 no matter what endianness */
return c;
- Get/clear the lowest bit of 1 (or 0 by using ~x as input)
x & -x; and x & (x-1);
- Get the index of lowest/highest bit of 1
k = 0;
if ((x & 0x1) != 0) return k;
do { ++k;} while (((x >>= 1) & 0x1) == 0) and
while (x >>= 1) ++k;
- Calculate the number of '1' in the one integer
while (x != 0)
{ x = x & (x-1); ++count; }
- Check whether the integer is the power of 2
The number of '1' in the integer is one.
- Get the next power of 2
unsigned int n = 1U << highestOne(x);
if (n == x) return n;
return n << 1;
- Reverse the bits order in one integer
x = ((x & m) << n) | ((x & ~m) >> n); /* m is masking code and n is swapping number */
- Reverse two bits in one word: swap2(x, k1, k2)
- Arithmetic Rotation
x = (x << r) | (x >> (BITNUM - r));
- Circular Block Shifting
x = (1 << n) - 1;
x = x << p | (x >> (BITNUM - p));
- Max(0, x) and Min(0, x)
return x & ~(x >> (BITNUM - 1)); and
return x & (x >> (BITNUM - 1))
- Overflow for signed num
addition: ~(a^b)&(a^s)&0x80000000
subtraction: (a^b)&(a^s)&0x80000000

String And Array

* Examples
- To get the first letter which is not repeated in the string
Build the key index between character and its occurrence with array or hashtable.
- Remove the specified characters in the string
Build the key index between character and its status (stay or removed). In place deleting operation with two pointers.
- Reverse the order of a sequence of words separated with space OR circularly shift the string
In place reverse with single word reverse after getting the start and end of words.
- Conversion between signed integer and string
1) To convert between char 0~9 and its integer with the aid of '0'
2) Accumulate in the conversion of atoi from left to right
3) Separate digits in the conversion of itoa from right to left and so reverse order output
- Merge two sorted arrays with the length of M and N (M>>N)
Binary search in M

Tree

* Binary Search Tree
- Search in BALANCED BST: O(logN)
- Insert and delete in BALANCED BST: O(logN)
- Obtain the parent node for a given node: O(logN)
- How to get maximal and minimal value in BST
- Output all the nodes SORTED in BST: O(N)
- Recursive algorithm associated

* Heap: Complete Binary Tree
- Implemented efficiently by an array due to its order and shape properties
- Insert, delete_min/max and delete: O(logN)
- Increase and decrease key: O(logN)
- Build heap: O(NlogN)
- Search in heap: O(N)

* Traversal
Preorder, DFS, postorder, in-order, and BFS

* Set
A set contains a sorted set of unique objects, which is usually implemented by BST.

* Examples
- Preorder traversal of BST without recursion
Stack is used to store the intermediate variables.
- Find the lowest ancestor of two nodes in one BST
The one with value between these two nodes would be the answer.
- Find the first K largest numbers or to find a subset of K numbers which sums up to at most T
Partial sort with one heap of K units.
- Find the K largest/smallest number in a heap of N elements with O(KlogK)/O(1). K is much less than N
- Construct a Huffman code and compute the sum of a large set of floating point number

List

* Single Linked List
- One Head Pointer Must Be Associated
To change the head pointer in one sub-routine, the pointer itself instead of its copy must be changed. Therefore the pointer to head pointer must be passed in ANY sub-routines which changes the head/tail pointers.
- Lists End With NULL
This must be checked when the traverse happens.
- Insert And Delete
When deleting one element in the list, the element before this one must be obtained.
When inserting one element, it depends on whether it is inserted before or after a specific element.
- Free Every Element in The List
- Special Cases Processing: Head and Tail; Length of List == 0, 1, 2, ...

* Examples
- Implement stack data structure
We could implement stack with variable array or single linked list. Due to the heavy overhead of maintaining the memory of elements, variable array might be suitable for small data set.
- Insert and delete function in list with head and tail pointers
How to process special cases?
- Get the mth element in reverse order in one list
1) n = N - m; Two traverses to get N and n; O(N)
2) Two pointers with the distance of m
- How to check if the list contains loop?
Fast and slow pointers
- How to delete one element if only the pointer to this element is given, i.e. without traversing?
Copy the content of next element to this one and delete next element.
- How to reverse one list with/without recursion?

Sync in MPEG

* SCR/PCR, PTS and DTS
Sync in MPEG is handled at the packet layer (PES), with the SCR/PCR, PTS and DTS field serving as instruments. The timing base of them is 90KHz (27MHz/300). They are not necessarily encoded for each video frame or audio presentation unit, but are only required to occur with intervals not exceeding 0.7s/700ms for periodic updating of the decoders' clocks, i.e., the maximal length of pack in PS is 0.7s. For B frames of video and audio packet, the PTS is equal to its DTS. In the case of I and P pictures only, they are the same too. In general, I and P frames of video have a reordering delay (until next I/P frame comes) between DTS and PTS. The PTS actually could be interpolated based on the above information.

* Sync Using A Master Stream
All of the media streams being decoded and displayed must have exactly one independent master. Each of the individual media display units must slave the timing of their operation to the master stream. The master stream may be chosen depending on the application. Whichever media stream is the master, all the media streams bu the master must slave the timing of their respective displays to the PTSs extracted from the master media stream.

Audio is always chosen to be the master in MPEG decoding. The audio stream will be played back continuously with the clock being continually updated to equal the PTS value of the audio unit. In particular, the STD clock is typically initialized to be equal to the value encoded in the first SCR/PCR field when it enters the decoder's buffer. Thereafter the audio decoder controls the STD clock by updating this clock with the PTS value (coarse sync without PLL, in constrast, fine sync would PLL 27MHz with the PTSs).

The other decoders simply use the audio-controlled clock to determine the correct time to present their decoded data, at the times when their PTS are equal to the current value of the clock. Therefore, if the sync is missed, video picture would be skipped or repeated but audio unit never.

Extern "C"

Extern "C"
* It is used for C/C++ mix programming. Two aspects it has:
- All the variables and functions it is with are extern
- All of these are compiled and linked with C methods

* C and C++ Object Name
- Functions and variables in C are identified by their names
- Functions and variables in C++ are identified by their name, input arguments, return value and class name associated, etc. by combined, due to the overloading and other features in C++.

* Usage
It is only used in C++ header file and can not be included in C files.
- When C++ uses C header files, use the following in the C++ header file:
extern "C"
{
     #include "xxx.h"
}
The C++ files must include this header file instead of using extern directly for C variables and functions.
- When C uses C++ header files, use extern instead of including the C++ header file:
cppfile.h:
extern "C"
{
     void xxx(void);
}
cfile.c
extern void xxx(void);

* _cplusplus
In order to share this header file by C and C++, the macro _cplusplus is used to wrap the extern "C":
#ifdef _cplusplus
extern "C"{
#endif
... ... ...
#ifdef _cplusplus
}
#endif

Abstraction Relationship

* Three Relationships In General
- is-a
The public inheritance. Derived class is a special base class and could be used in any circumstances of base class. This is the key point of dynamic binding. On the contrary, base class is not derived class.
- has-a
The composite implementation with the handles to composite objects.
- use-a
Two classes interact at some time instant. No private inheritance implementation and use composite implementation with the handles to used objects.

* Has-a and Usa-a
It is difficult to distinguish these two relationships from the coding since it is generally using the handles to implement them. For has-a, the master class has the responsibility to create, maintain and delete its composite object. For use-a, the useful object might be shared with others. The setting of handles to comp might be these:
- Has-a
{ delete comp; comp = newcomp; }
{ delete comp; comp = newcomp->clone(); }
- Use-a
{ comp = newcomp; }

C++ Dynamic Binding

* C++ Dynamic Binding
- Implemented by public inheritance and virtual functions
- Base and derived classes: general and special
- Base class must have one virtual function at least and it is the destructor. This affects the following two points.
- Virtual pointer to the virtual function table and its implementation in the derivation.
- Conversion/casting between base class object and derived class object.
- Public inheritance preferred. Use composite instead of private inheritance. No protected inheritance.
- Distinguish function overload, override, and hidden.

* Inheritance
- Base class consists of public interface (public accessibility) and private interface for derived classes (public and protected accessibility)
- Pure virtual function allows only interface without implementation for derived class.
- Virtual function allows interface with default implementation for derived class.
- Non-virtual function allows interface with mandatory implementation for derived class.

* Virtual Function
- Virtual function can not be static
- Redefine all the overloaded virtual functions
- No default arguments for virtual functions
- No virtual copy and assignment operator
- No virtual function calling in the constructor and destructor

* Abstract Class and Virtual Base Class

C++ Data Abstraction

* Abstract Data Type (class and object)
- Public interface
- Private implementation and private interface for derived classes

* Class
The following is very important for the abstract data type. They might be generated by compiler and could not be derived (not be virtual except destructor). (Note another one which can not be derived is the hidden data member or member function.)
- Constructor
1) Use initialization list in the constructor as much as possible to improve initialization efficiency. Const and reference must be put in the list while static and array member must not. Base class, const, reference and object members must be initialized.
2) Note the consistent order of member initialization.
3) Constructor with only one input or default inputs performs implicit casting.
4) Direct initialization instead of copy initialization, for example,
X a(10);
X a = X(10);
x a = 10;

- Destructor
1) If the class is designed for being derived, destructor must be virtual to allow the correct destructor to be called with dynamic binding and uniform data type mapping in memory. If not, do not declare it as virtual to save memory.
2) Even the destructor is pure virtual function, it still needs to be defined and it is allowed.

- Copy constructor
1) If some handle to object/memory outside the object is contained, the copy constructor must be redefined.
2) Each member must be copied explicitly in the copy constructor, esp. the base class.
3) The standard format for copy constructor
X(X const &x)
4) Put it in the private area without new definition to avoid use it illegally.

- Assignment operator
Note the difference of initialization and assignment.
1) If some handle to object/memory outside the object is contained, the assignment operator must be redefined. Delete the original memory allocation and reallocate and assign it.
2) The self assignment must be checked.
if (this != that) ...
3) Each member must be assigned explicitly in the assignment operator, esp. calling the assignment operator of base class.
B::operator =(that);
4) The standard format for assignment operator
X const &operator=(X const &x)
5) Put it in the private area without new definition to avoid use it illegally.