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