Category: Paste

汉诺塔游戏

前天在一次面试中，面试官问到我汉诺塔(Towers of Hanoi)的问题，当时只知道是递归，知道手动玩游戏怎么玩，写程序还真的忘记了。大学我记得是有写过这样的作业，还有八皇后等等，不过真的都还给老师了，哈哈哈！

然后回家看了下，
http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html
http://www.python-course.eu/towers_of_hanoi.php

汉诺塔的介绍参见http://en.wikipedia.org/wiki/Tower_of_Hanoi等等

程序如下，

#include <stdio.h>

void move(char src, char dest)
{
	printf("\nMove the top plate of %c to %c", src, dest);
}

void hanoi(int n, char a, char b, char c)
{
	if (n == 1) { // 递归结束
		move(a, c); // 最小的那个盘子
	} else {
		hanoi(n - 1, a, c, b); // step 1，把所有小于最大的盘子移动到临时的柱子上(可以借助目的柱子)
		move(a, c); // step 2，把最大的盘子移动到目的柱子上
		hanoi(n - 1, b, a, c); // step 3，把临时的柱子上的盘子移动到目的柱子上(可以借助原始柱子)，和step 1的方式一模一样

							// step 1和3都会有递归产生
	}
}

int main()
{
	int n;
	printf("\nPlz input number of the plates:");
	scanf("%d", &n);
	printf("\nMoving %d plates from A to C:", n);

	hanoi(n, 'A', 'B', 'C');

	printf("\nDone!\n");
}

如果你能看懂上面的注释，很好。如果你看不懂，也没关系，现在我们来试着详细点解释这个问题。
我们先来玩这个游戏，如图(点击图片看正常大图)，
Towers of Hanoi
你会发现盘子的数量和最终要花费的步数是有关系的，为2^n – 1，也就是说只有1个盘子的时候需要1步，2个盘子的时候需要3步，3个盘子的时候需要7步，以此直到天荒地老。。。

所以这种思路我们是不是可以采用递归那完成呢？
比如3个盘子的时候，我们先移动上面的2个盘子(需要3步)，再移动最大的1个盘子(需要1步)，然后再移动那2个盘子到最大的盘子上面(需要3步)，加起来一共就是7步，刚刚好。
并且2个盘子也可以同理拆分，最终会变成1个盘子的情况，1个盘子的情况很好解决，就1步，别且这也就是边界情况。

看起来这样是可以，再回头来看看程序，
step 1 ~ 3是不是很清晰了，并且step 1和3自己又会有递归产生，继续拆分，直到最后都是1个盘子的时候，递归结束。

如果不关心内部细节是不是就这样完美结束了呢？确实，如果你不关心内部细节，这样已经让人很容易的理解这个问题。但是总归会有一部分人会继续深挖。
现在我们以3个盘子为例，以程序执行的角度来看，

hanoi(3, 'A', 'B', 'C')
{
	hanoi(2, 'A', 'C', 'B');
		hanoi(1, 'A', 'B', 'C')
			move('A', 'C')
		move('A', 'B')
		hanoi(1, 'C', 'A', 'B')
			move('C', 'B')
	move('A', 'C');
	hanoi(2, 'B', 'A', 'C');
		hanoi(1, 'B', 'C', 'A')
			move('B', 'A')
		move('B', 'C')
		hanoi(1, 'A', 'B', 'C')
			move('A', 'C')
}

好像也没什么好写的，有机会看看非递归的方式来实现。

P.S.
递归有风险，使用需谨慎！

C/CPP中的坑

记录C/CPP当中一些隐晦的问题，并非著名的C Traps and Pitfalls，虽然有可能包含一些相同的点。

1、类型退化(隐式转换)问题

#include <stdio.h>

#define SIZEOF(A) \
	sizeof(A) / sizeof(A[0])

inline static int sizeOfCharArray(char a[])
{
	return sizeof(a) / sizeof(a[0]); // type casting by default
}

int main(int argc, char **argv)
{
	char a[10];
	a[0] = 5;
	a[9] = 8;

	void *p = &a; // do it explicitly

	printf("sizeof char array %d %lu %lu\n", sizeOfCharArray(a), sizeof((char*) p), SIZEOF(a));

	return 0;
}

注意这段程序当中sizeOfCharArray方法，其实在很多情况都会有隐式转换，但是和sizeof一起用的时候要注意。

2、多层循环，效率问题
http://rednaxelafx.iteye.com/blog/352730

H.264预测之帧间预测

这是一篇阅读笔记，直接点击图片可以查看清晰大图。

参考资料
The H.264 Advanced Video Compression Standard, Second Edition，以下简称THAVCS
Information technology – Coding of audio-visual objects – Part 10: Advanced Video Coding，以下简称SPEC

CodecVisa
JM
foreman_part_qcif.264 这个是foreman_part_qcif.yuv通过JM 8.6转换来的

http://blog.csdn.net/stpeace/article/details/8115392

帧间预测就是以已经编码好的帧(在display order上可以是当前帧的前面也可以是后面)作为参考帧，确定预测区域，生成预测块，计算出殘差，这些参考帧都存放于Decoded Picture Buffer当中。与帧内预测不同的是，帧间预测是以重建的帧为预测帧的，而帧内预测是一Loop filter之前的帧为预测帧。当前区块和预测区域之间的位移为运动向量(Motion Vector，简写为MV)，每个区块有各自的MV，并且MV可以是整数精度，二分之一精度或者四分之一精度(对于4:2:0的视频，C是八分之一精度)，这种非整数精度的预测区域都是通过插值算法从参考帧当中计算出来的。

注意，在实际当中MV的单位都是以最小的精度为单位的，比如Y分量的MV单位就是四分之一精度，C分量的MV单位就是八分之一精度，当然这里说的都是4:2:0的视频。

主要过程就是选取参考帧，插值，确定预测区块，确定预测类型，确定运动向量，预测运动向量，编码运动向量差量和殘差，deblocking filter。。。
这里插值计算需要注意的是，先计算二分之一，再计算四分之一，参见THAVCS 6.4.2.1 Generating interpolated sub-pixel samples。

我们来看个实例，先看MV值为整数的，也就是不用插值的。

跟帧内预测所用的码流一样，用CodecVisa打开，选取第二帧(这个码流一共三帧，分别为IPP)，选取第4行，第9列的那个MB。
看图inter-prediction-p-slice，
inter-prediction-p-slice
因为这里Y分量MV单位是四分之一精度，所以实际值除以4就是像素偏差。被高亮的块的值向左移动7个像素就刚刚和第一帧当中被高亮位置的值相等，这也就是说当前块是以第一帧所示区块为预测块的，注意帧间预测的参考帧都是重构出来的，都是看Final值，和帧内预测看Pre-LP值不一样，如图inter-prediction-reference-picture，
inter-prediction-reference-picture
这是帧间预测的一个实例。

再来看看非整数精度的情况，MV为(-2.75, -2)，垂直方向上是整数，我们不用考虑，现在就看水平方向上。
inter-prediction-p-slice-non-integer-pixel
inter-prediction-reference-picture-non-integer-pixel
如上两张图就分别是当前块和预测块，因为这个MV不是整数的，所以要先插值算出预测块，我们把有需要的数据提取出来，

187    185    187    195 A   199    201    200    200

187    184    191    198 B   199    201    199    200

188    183    174    169 C   183    202    198    200

189    185    166    130 D   132    172    199    202

如上数据就是参考帧重构后的数据，A，B，C和D就是我们要插值算出来的数据，也就是当前块的预测值。

先计算二分之一

Aa = round((1 * 185 - 5 * 187 + 20 * 195 + 20 * 199 - 5 * 201 + 1 * 200) / 32) = 198
Bb = round((1 * 184 - 5 * 191 + 20 * 198 + 20 * 199 - 5 * 201 + 1 * 199) / 32) = 199
Cc = round((1 * 183 - 5 * 174 + 20 * 169 + 20 * 183 - 5 * 202 + 1 * 198) / 32) = 173
Dd = round((1 * 185 - 5 * 166 + 20 * 130 + 20 * 132 - 5 * 172 + 1 * 199) / 32) = 123

然后四分之一

A = round((198 + 195) / 2) = 197
B = round((199 + 198) / 2) = 199
C = round((173 + 169) / 2) = 171
D = round((123 + 130) / 2) = 127

第二列的数据，方法同样
先计算二分之一

Aa + 1 = round((1 * 187 - 5 * 195 + 20 * 199 + 20 * 201 - 5 * 200 + 1 * 200) / 32) = 200
Bb + 1 = round((1 * 191 - 5 * 198 + 20 * 199 + 20 * 201 - 5 * 199 + 1 * 200) / 32) = 200
Cc + 1 = round((1 * 174 - 5 * 169 + 20 * 183 + 20 * 202 - 5 * 198 + 1 * 200) / 32) = 195
Dd + 1 = round((1 * 166 - 5 * 130 + 20 * 132 + 20 * 172 - 5 * 199 + 1 * 202) / 32) = 150

然后四分之一

A = round((200 + 199) / 2) = 200
B = round((200 + 199) / 2) = 200
C = round((195 + 183) / 2) = 189
D = round((150 + 132) / 2) = 141

后面的就不再罗列了，从结果来看，我们这里预测的结果

197    200    ....
199    200    ....
171    189    ....
127    141    ....

和CodecVisa有些许出入，但是变化趋势相同的，所以这个实验的基本目的达到了。

Exponential-Golomb coding

参考资料：
http://en.wikipedia.org/wiki/Exponential-Golomb_coding
http://zh.wikipedia.org/zh/指数哥伦布码
Information technology — Coding of audio-visual objects — Part 10: Advanced Video Coding

摘抄自以上资料，简单总结。

指數哥倫布碼(Exp-Golomb code)，一种壓縮編碼方法。
用来表示非负整数的k阶指数哥伦布码可用如下步骤生成：
1. 将数字以二进制形式写出，去掉最低的k个比特位，之后加1
2. 计算留下的比特数，将此数减一，即是需要增加的前导零个数(注意是比特位数，非该比特串表示的值)
3. 将第一步中去掉的最低k个比特位补回比特串尾部
0阶指数哥伦布码如下所示：

0 => 1 => 1
1 => 10 => 010
2 => 11 => 011
3 => 100 => 00100
4 => 101 => 00101
5 => 110 => 00110
6 => 111 => 00111
7 => 1000 => 0001000
8 => 1001 => 0001001
...

从二进制比特串形式来看，0阶哥伦布编码的码字(codeword)由3部分构成：
码字 = [M个0] + [1] + [内容]
内容也是M位数据，所以每个0阶哥伦布码的位的长度为2M + 1，每个码字由原始的数字(codenumber)产生。

比如上面的数字7，二进制表示为111，0阶编码，所以不用去最后的比特为，加1之后变成1000，比特数为4位，所以前缀需要增加3(4-1)个0，即0001000，0阶所以结尾也不需要补码，于是最终码字就为0001000。

那如何解码呢？
参见如下伪代码

leadingZeroBits = −1
for (b = 0; !b; leadingZeroBits++)
	b = read_bits(1)

codeNum = 2^(leadingZeroBits + k) − 2^k + read_bits(leadingZeroBits + k)

这里类似于2^k这种写法表示幂运算，对于通常H.264当中用的是0阶的，所以可以简化成如下图

Exponential-Golomb Decoding

这里read_bits(…)的返回值使用高位在先的二进制无符号整数表示

二进制比特串       长度             解析值
1001             1               0
001 1001         5               5
01 1010          3               2
010              3               1
000 1011         7               10
0001 001         7               8

如上表，传入的比特串可能多余实际需要的数据，我们只需要解析需要的部分就可以了。

P.S.
为什么叫做指数哥伦布编码？
因为它对信源符号的分组大小按照指数增长。

二叉树

炒现饭的帖子，内容均来自于网络或者书籍整理。

I)树
它是由N(N>=1)个有限结点组成一个具有层次关系的集合，它具有以下的特点：
a)每个结点有零个或多个子结点，没有子节点的节点称为叶节点(通常称为叶子)
b)没有父结点的结点称为根结点(通常称为根)
c)每一个非根结点有且只有一个父结点(没有多个引用指向同一个节点)
d)除了根结点外，每个子结点可以分为M个不相交的子树

|
r        55
o       /  \
o      /    \
t     88     3
.           /|\
.          / | \
.         67 7 23
l        / \     \
e       /   \     \
a      53    5     9
f
|

        Figure. A

如上图(Figure. A)，它像一棵自然界中倒生长的树，每个枝丫处就是一个节点，方向是由根到叶子，它实际上是一个有向图。

这里我们介绍下节点，节点是包含一个数据项和一个(多个)指向其他节点的引用项的数据结构/记录，通常我们用类似如下代码来表示一个节点：
1)

record SinglyLinkedNode {
    next, // A reference to the next node
    data // Data or reference to data
}

2)

record DoublyLinkedNode {
    previous, // A reference to the previous node
    next, // A reference to the next node
    data // Data or reference to data
}

3)

record BinaryNode {
    parent, // A reference to the parent node                                
    left_child, // A reference to the left child node
    right_child, // A reference to the right child node
    data // Data or reference to data
}

结合上图(Figure. A)我们就很好理解了。

一些有关树的基本概念：
节点的度(node’s degree): 子节点的个数叫做节点的度
树的度: 一棵树中，最大的节点的度称为树的度
节点层次(level): 根为第一层，根的子节点为第二层，以此类推
数的高度或深度(depth): 树中最大的节点层次
兄弟节点(siblings): 具有相同父节点的节点
森林: M(M>=0)棵互不相交的树的集合(删去一棵树的根，就得到一个森林；加上一个结点作树根，森林就变为一棵树)
有序树(ordered tree)/无序树(unodered tree): 若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(ordered tree)；否则称为无序树(unodered tree)
还有诸如子孙/祖先/堂兄弟节点这些概念就不列举了

上图(Figure. A)当中，树的度是3，67节点的度是2，数的深度是4，55节点是根节点等等这些基本属性我们就能很快得出。

II)二叉树
每个结点最多有两个子树的有序树，通常有左子树(left subtree)和右子树(right subtree)，最大的节点的度为2，也就是二叉树的度为2。

满二叉树(full binary tree): 有时被称为proper binary tree或者2-tree或者strictly binary tree，就是每个节点有0或2个子节点。

完全二叉树(complete binary tree): 除了最后一层之外的其他层次(当然也可能包含最后一层)，每个节点都包含2个子节点，并且所有节点都尽可能靠左排列

平衡二叉树: 如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树

二叉树的遍历，前序(pre-order)，中序(in-order)和后序(post-order)，前序是根左右，中序是左根右，后序是左右根。

一些有关二叉树的常用算法参看http://blog.csdn.net/luckyxiaoqiang/article/details/7518888

几个简单的例子:

这里的代码实现都是简单易懂的实现，帮助理解概念，没有做过优化！

参考资料:
http://en.wikipedia.org/wiki/Tree_(data_structure)
http://en.wikipedia.org/wiki/Node_(computer_science)
http://en.wikipedia.org/wiki/Branching_factor
http://en.wikipedia.org/wiki/Binary_tree

http://zhedahht.blog.163.com/blog/static/25411174201142733927831/

JPEG学习笔记

阅读资料:
JPEG File Interchange Format Version 1.02
JEITA CP-3451 Exif Version 2.2
DIGITAL COMPRESSION AND CODING OF CONTINUOUS-TONE STILL IMAGES – REQUIREMENTS AND GUIDELINES
The JPEG Still Picture Compression Standard
JPEG 简易文档 V2.15 云风
libjpeg 6b
JPEG 原理详细实例分析及其在嵌入式 Linux 中的应用 http://www.ibm.com/developerworks/cn/linux/l-cn-jpeg/
JPEG文件编/解码详解 http://blog.csdn.net/lpt19832003/article/details/1713718
Huffman 编码压缩算法 http://coolshell.cn/articles/7459.html
A SIMPLE EXAMPLE OF HUFFMAN CODING ON A STRING http://nerdaholyc.com/a-simple-example-of-huffman-coding-on-a-string/

这是一篇自己学习JPEG的笔记，会不断完善，多数是别人的啦，少许自己理解，如有理解错误还请指出！

1、JPEG File格式分为两个部分：标记码和压缩数据
标记码由2个字节组成，以0xFF打头，后面的一个字节根据含义不同而定。每个标记码之前还可以加任意个0xFF来填充，他们没有什么意义，也就是说连续的多个0xFF被解释成一个0xFF。

2、
压缩算法是JPEG
色彩空间是YCbCr
APP0标记码是必须的

字节序都是大端

YCbCr的Cb和Cr一般都是有符号数，但是在JPEG当中都是无符号数，所以目前在JPEG当中的做法是RGB到YCbCr的转换是计算好Cb和Cr之后将其值增加128，再做后续的运算。
YCbCr到RGB的计算是先将Cb和Cr的值减去128后再来做转换。

假设一个数据单元，8 x 8的原始图像如下(转化为YCbCr之后的数据)：

52   55   61   66   70   61   64   73

63   59   55   90   109  85   69   72

62   59   68   113  144  104  66   73

63   58   71   122  154  106  70   69

67   61   68   104  126  88   68   70

79   65   60   70   77   68   58   75

85   71   64   59   55   61   65   83

87   79   69   68   65   76   78   94

3、DCT(Discrete Cosine Transform)
在做FDCT(Forward DCT)变换的时候，Y，Cb和Cr的值都范围都是-128 ~ 127，所以都要被减去128。
适配范围，每个点都减去128：

-76  -73  -67  -62  -58  -67  -64  -55

-65  -69  -73  -38  -19  -43  -59  -56

-66  -69  -60  -15  16   -24  -62  -55

-65  -70  -57  -6   26   -22  -58  -59

-61  -67  -60  -24  -2   -40  -60  -58

-49  -63  -68  -58  -51  -60  -70  -53

-43  -57  -64  -69  -73  -67  -63  -45

-41  -49  -59  -60  -63  -52  -50  -34

使用FDCT并四舍五入取最接近的整数：

-415 -30  -61  27   56   -20  -2   0

4    -22  -61  10   13   -7   -9   5

-47  7    77   -25  -29  10   5    -6

-49  12   34   -15  -10  6    2    2

12   -7   -13  -4   -2   2    -3   3

-8   3    2    -6   -2   1    4    2

-1   0    0    -2   -1   -3   4    -1

0    0    -1   -4   -1   0    1    2

DC(Direct Current)/AC(Alternating Current)
什么是DC？什么是AC？

4、量化：

-26  -3   -6   2    2    -1   0    0

0    -2   -4   1    1    0    0    0

-3   1    5    -1   -1   0    0    0

-4   1    2    -1   0    0    0    0

1    0    0    0    0    0    0    0

0    0    0    0    0    0    0    0

0    0    0    0    0    0    0    0

0    0    0    0    0    0    0    0

0    0    0    0    0    0    0    0

5、Zigzag
Zigzag的好处，在内存当中连续的点在图片上也是相邻的了，而且后面都是连续的0，可以继续使用RLE压缩。
于是就变成：

−26,−3,0,−3,−2,−6,2,−4,1,−4,1,1,5,1,2,−1,1,−1,2,0,0,0,0,0,−1,−1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

实际上我们的DC系数在编码的时候不会算到Zigzag里面，因为DC系数值比较大，并且相邻的两个数据单元的DC差值不会很大，所以JPEG使用了差分脉冲调制编码(DPCM)对相邻两个数据单元之间的DC系数进行差值编码，这是利用了两个数据单元之间的相关性。
对其他的63个AC系数会采用Zigzag编码。

6、RLE(Run Length Coding)
我们来用一个简单的例子来详细说明一下，假设以下是使用Zigzag编码过的63个AC系数数据：
57,45,0,0,0,0,23,0,-30,-16,0,0,1,0,0,0,0,0,0,0,..,0
可以表示为
(0,57) ; (0,45) ; (4,23) ; (1,-30) ; (0,-16) ; (2，1) ; EOB
EOB实际就是结束，也可以用(0,0)表示，如果最后面不是以0结束的就不需要
解释下这个含义，编码后的含义就是说在57之前有0个0，在45之前有0个0，在23之前有4个0，在-30之前有1个0，以此类推。
需要值得注意的是，我们后面还会对这样的数据使用Huffman压缩，但是该算法要求这个表示0的个数的值的位数是4bit，也就是说能保存的值的范围是0 ~ 15。
所以碰到连续大于15个0的情况的时候，我们会拆分(15,0) ; (3,2) ; … ; (15,0) ; (15,0) ; (1,4)，用(15,0)表示连续的16个0，也就是表示：
19个0,2, … ,33个0,4。

7、Canonical Huffman Code
在做好这些工作之后，JPEG还会对数据进行压缩，利用Canonical Huffman Code编码，对出现频率更高的数据采用更短的码字来编码。
这里将数值按照位数分为了16组。

               数值                 组              实际保存值
                0                   0                   -
              -1,1                  1                  0,1
           -3,-2,2,3                2              00,01,10,11
     -7,-6,-5,-4,4,5,6,7            3    000,001,010,011,100,101,110,111
       -15,..,-8,8,..,15            4       0000,..,0111,1000,..,1111
      -31,..,-16,16,..,31           5     00000,..,01111,10000,..,11111
      -63,..,-32,32,..,63           6                   .
     -127,..,-64,64,..,127          7                   .
    -255,..,-128,128,..,255         8                   .
    -511,..,-256,256,..,511         9                   .
   -1023,..,-512,512,..,1023       10                   .
  -2047,..,-1024,1024,..,2047      11                   .
  -4095,..,-2048,2048,..,4095      12                   .
  -8191,..,-4096,4096,..,8191      13                   .
 -16383,..,-8192,8192,..,16383     14                   .
-32767,..,-16384,16384,..,32767    15                   .

之前RLE之后的结果：
(0,57) ; (0,45) ; (4,23) ; (1,-30) ; (0,-16) ; (2，1) ; EOB
现在仅对后面的值进行变换，前面表示0的个数的值不动。

    57是第6组的，实际保存值为111001，所以被编码为(6,111001)
    45，同样的操作，编码为 (6,101101)
    23  ->  (5,10111)
   -30  ->  (5,00001)
    -8  ->  (4,0111)
     1  ->  (1,1)

前面的那串数字就变成了:
(0,6), 111001 ; (0,6), 101101 ; (4,5), 10111; (1,5), 00001; (0,4) , 0111 ; (2,1), 1 ; (0,0)

括号里的数值正好合成一个字节，后面被编码的数字表示范围是-32767 ~ 32767。
合成的字节里，高4位是前续0的个数，低4位描述了后面数字的位数。

接着变，下面的变化就需要去查找Huffman编码表了，这个是在压缩之前就应该构建好的，这个表是将0 ~ 255的8位定长数根据其出现的频率不同映射成为1 ~ 16位不定长数，频率大的小于8位，频率小的高于8位。这点很重要，当然这个表是如何构建出来的也很重要。
现在我们假设查表得知：

 6 = (0,6)    ---  111000    (注: 6 = 0 * 16 + 6 = 0x06)
69 = (4,5)    ---  1111111110011001    (注: 69 = 4 * 16 + 5 = 0x45)
21 = (1,5)    ---  11111110110
4  = (0,4)    ---  1011
33 = (2,1)    ---  11011
 0 = EOB = (0,0) ---  1010

那么最终我们得到的AC系数按位流就如下：
111000 111001 111000 101101 1111111110011001 10111 11111110110 00001 1011 0111 11011 1 1010

好奇：看起来前面括号里用的编码(范围为0 ~ 255)和后面编码的数字范围为-32767 ~ 32767的来自不同的编码基础？这样不会混淆么？
前面的编码数据(也就是说之前组合起来的一字节的数据，高4位0的个数，低4位非0数据编码后所占的位数)可以根据Huffman表查询出来，这样我们就可以得到紧跟着的数据的位数，读取相应的数据，所以不会混淆。

8、DC编码
DC在每个数据单元之中只有一个，并且连续数据单元之间的DC有紧密的联系，所以JPEG当中就采用的差分脉冲调制编码(DPCM)。
相邻单元之间
Diff = DC(i) – DC(i-1)
所以
DC(i) = DC(i-1) + Diff

我们保存的DC都是和上一个DC的差值，所以DC(0)等于多少？云风说是0，我觉得不应该啊。
目前DC相关这部分需要进一步证实。
假设Diff为-511
就会被编码成(9, 000000000)
假设查表(一般在JPEG文件当中Y和C是不同的表，另外还分DC和AC，所以通常就有4个Huffman表)的9的Huffman编码为1111110，那么整个DC的二进制表示就为1111110 000000000。

将DC的数据流放到AC之前就可以组成完整的编码数据流。

1111110 000000000  111000 111001  111000 101101  1111111110011001 10111  11111110110 00001  1011 0111  11011 1  1010

9、疑问：
MCU和DU之间有关系吗？看起来这些压缩都是在DU当中进行的。
每个Y，Cb，Cr分量都要来这样压缩一次吗？还是3个分量一起压缩？或者说是可以根据采样的不同，将部分分量放在一起压缩，比如Cb和Cr一起压缩，Y单独压缩。
看起来Cb可以和Cr放在一起压缩。
UPDATE：
MCU可能有一个或者多个DU组成，压缩都是按DU来的，分量都是分开压缩的，一个MCU当中的Y，Cb，Cr都是分别压缩的，然后按MCU组装成字节流。

10、JFIF文件格式分析实例：

SOI(Start of Image)

APP0(JFIF application segment)

APP1(application reserved)
…
APP15

DQT(Define Quantization Table)

DHT(Difine Huffman Table)

SOF(Start of Frame)

SOS(Start of Scan)

EOI(End of Image)

IFD(Image File Directories)

标记的前2个字节为名字，也就是前面所说的标记码，接着的2个字节为该标记的所占空间大小(不包含标记名字的2个字节，但包含自己在内)
比如这一段数据
FF E0 00 10 4A 46 49 46 00 01 01 00 00 01 00 01 00 00
当中
0xFFE0为标记码，也就是APP0
0x0010为该标记所占大小，也就是16
后面跟的14个字节(“4A 46 49 46 00 01 01 00 00 01 00 01 00 00”)就是标记内容
根据SPEC的描述：
5字节为标识符，这里就是JFIF0
2字节为版本号(主版本和次版本各占1个字节)，这里就是1.01
1字节为密度单位，0表示没有单位，1表示每英寸点数，2表示每厘米点数
2字节为水平像素密度，这里是1
2字节为垂直像素密度，这里是1
1字节为缩略图水平像素总数，这里是0
1字节为缩略图垂直像素总数，这里为0
如果没有缩略图，这两个缩略图相关的字段值都必须要为0，如果不为0就表示后面还有缩略图的RGB数据，大小是3字节的倍数。

对于DQT

FF DB 00 43 00 08 06 06 07 06 05 08 07 07 07 09 09 08 0A 0C 14 0D 0C 0B 0B 0C 19 12 13 0F 14 1D 1A 1F 1E 1D 1A 1C 1C 20 24 2E 27 20 22 2C 23 1C 1C 28 37 29 2C 30 31 34 34 34 1F 27 39 3D 38 32 3C 2E 33 34 32
FF DB 00 43 01 09 09 09 0C 0B 0C 18 0D 0D 18 32 21 1C 21 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32

0xFFDB为标记码
0x0043为所占大小，也就是67(除去本身所占2字节，大小跟精度有关)
1个字节为QT信息，高4位为QT精度，低4位为QT号
还原成矩阵形式(Zigzag)

8   6   5   8   12  20  26  31

6   6   7   10  13  29  30  28

7   7   8   12  20  29  35  28

7   9   11  15  26  44  40  31

9   11  19  28  34  55  52  39

12  18  28  32  41  52  57  46 

25  32  39  44  52  61  60  51

36  46  48  49  56  50  52  50

就是这样(JPEG 原理详细实例分析及其在嵌入式 Linux 中的应用这篇文章中应该画错了)
另外一个QT也是同样的方法可以还原。

对于SOF0这段数据
FF C0 00 11 08 00 95 00 E3 03 01 22 00 02 11 01 03 11 01
当中
0xFFC0表示SOF0
2个字节为长度，0x0011，即17
1个字节为数据样本的精度，这里是8位
2个字节表示图像的高度，这里是149
2个字节表示图像的宽度，这里是227
1个字节表示颜色分量数，JPEG都是YCrCb，即3
9个字节表示颜色分量信息，这里字节数是颜色分量数 multiply 3
因为分量信息中颜色分量ID占用1个字节，水平/垂直因子占用1个字节(高4位水平，低4位垂直)，量化表占用1个字节
H 2:1:1
V 2:1:1
所以总体采样因子就是(2 * 2):(1 * 1):(1 * 1)，即4:1:1

MCU宽是水平采样因子最大值 multiply 8(记该最大值为Hmax)
MCU高是垂直采样因子最大值 multiply 8(记该最大值为Vmax)
因此这里就是(Hmax * 8):(Vmax * 8) = 16:16

如果整幅图片的高度或者宽度不是MCU的整数倍，就需要padding，解码之后丢弃大于宽度或者高度部分的数据

在数据流当中，MCU是按从左到右，从上到下来排列的。

因为每个MCU由若干数据单元组成，而数据单元又必须是8:8的，所以MCU当中数据单元的个数就是4(Hmax * Vmax)

对于DHT，如下就有4个Huffman表

FF C4 00 1F 00 00 01 05 01 01 01 01 01 01 00 00 00 00 00 00 00 00 01 02 03 04 05 06 07 08 09 0A 0B
FF C4 00 B5 10 00 02 01 03 03 02 04 03 05 05 04 04 00 00 01 7D 01 02 03 00 04 11 05 12 21 31 41 06 13 51 61 07 22 71 14 32 81 91 A1 08 23 42 B1 C1 15 52 D1 F0 24 33 62 72 82 09 0A 16 17 18 19 1A 25 26 27 28 29 2A 34 35 36 37 38 39 3A 43 44 45 46 47 48 49 4A 53 54 55 56 57 58 59 5A 63 64 65 66 67 68 69 6A 73 74 75 76 77 78 79 7A 83 84 85 86 87 88 89 8A 92 93 94 95 96 97 98 99 9A A2 A3 A4 A5 A6 A7 A8 A9 AA B2 B3 B4 B5 B6 B7 B8 B9 BA C2 C3 C4 C5 C6 C7 C8 C9 CA D2 D3 D4 D5 D6 D7 D8 D9 DA E1 E2 E3 E4 E5 E6 E7 E8 E9 EA F1 F2 F3 F4 F5 F6 F7 F8 F9 FA
FF C4 00 1F 01 00 03 01 01 01 01 01 01 01 01 01 00 00 00 00 00 00 01 02 03 04 05 06 07 08 09 0A 0B
FF C4 00 B5 11 00 02 01 02 04 04 03 04 07 05 04 04 00 01 02 77 00 01 02 03 11 04 05 21 31 06 12 41 51 07 61 71 13 22 32 81 08 14 42 91 A1 B1 C1 09 23 33 52 F0 15 62 72 D1 0A 16 24 34 E1 25 F1 17 18 19 1A 26 27 28 29 2A 35 36 37 38 39 3A 43 44 45 46 47 48 49 4A 53 54 55 56 57 58 59 5A 63 64 65 66 67 68 69 6A 73 74 75 76 77 78 79 7A 82 83 84 85 86 87 88 89 8A 92 93 94 95 96 97 98 99 9A A2 A3 A4 A5 A6 A7 A8 A9 AA B2 B3 B4 B5 B6 B7 B8 B9 BA C2 C3 C4 C5 C6 C7 C8 C9 CA D2 D3 D4 D5 D6 D7 D8 D9 DA E2 E3 E4 E5 E6 E7 E8 E9 EA F2 F3 F4 F5 F6 F7 F8 F9 FA

2个字节为标记码
2个字节为长度
1个字节为类型和ID，高4位为类型，0为DC直流，1为AC交流；低4位为ID
也就是说这里有4个Huffman编码表，直流0，交流0，直流1，交流1
16个字节为码字的数量，以第一张表为例子，没有1位的码字，2位的码字1个，3位的码字5个，4到9位的码字各1个，没有9位以上的码字，所以一共是12个码字
剩下的12字节为编码内容(这12是根据码字数量得出的，1 + 5 + 1 + 1 + 1 + 1 + 1 + 1)，
00 01 02 03 04 05 06 07 08 09 0A 0B
所以转换成二进制的话就应当如下：

位数      代码                 码字
2         00                  00
3         01/02/03/04/05      001/010/011/100/101
4         06                  0110
5         07                  00111
6         08                  001000
7         09                  0001001
8         0A                  00001010
9         0B                  000001011

UPDATE: 这上面的编码内容的理解应该是错误的，这是参照http://www.ibm.com/developerworks/cn/linux/l-cn-jpeg/来的。
实际应该是：

Length    Code                Codeword    
2         00                  00
3         01                  010
3         02                  011
3         03                  100
3         04                  101
3         05                  110
4         06                  1110
5         07                  11110
6         08                  111110
7         09                  1111110
8         0A                  11111110
9         0B                  111111110

这个Huffman表是如何构建的，得好好研究，另外后面的压缩都会用到这个表的内容。
Huffman编码表的构建原理
第1个码字必须是0(根据其位数具体表现为0或00或000等等，以此类推)
下一个码字在前面一个的基础上加1，如果位数有增加，则加1之后补零到相应位数
值为00的为结束标志(EOB)，编码或者解码时候注意其码字

EXIF通常是放在APP1当中
FF E1 66 59 …… FF D9
0xFFE1(2字节)就是APP1的Marker名字，0x6559(2字节)是该字段的长度，为26201，但是不包含TAG名字所占用的2个字节。也就是说后面的实际内容占用了26199个字节，直到0xFFD9，这就是EXIF的内容。为什么会有个0xFFD9呢？我们都知道0xFFD9是EOI，因为EXIF里面的缩略图实际上也是一个完整的JPEG图片，它也有SOI等等这一些Marker。
参见JEITA CP-3451 Exif Version 2.2的Figure 7 Structure of Exif file with compressed thumbnail
因为EXIF并不是JPEG必须的，所以你把这之间的内容整个都拿掉(用16进制编辑器很好做到，有兴趣的可以试试看)，对图片也没有什么影响，只是少了所有EXIF的信息。

11、Linux下编译libjpeg
download source tree
uncompress it
cd to source tree folder
clean the source tree

$ ./configure --enable-shared --enable-static

Maybe it will complain this message
./configure: 1562: ./ltconfig: not found // Here
but it does not matter, so we do not care it.

$ make

if it complains ‘make: ./libtool: Command not found’
then fix your configure file from
LIBTOOL=”./libtool”
to
LIBTOOL=”libtool”
‘Cause under your current source tree, there is of course no file named libtool, so it can not exec that command, so replace it with the system-wide libtool. BUT the prerequisite thing is that you have installed libtool on your host machine.

Then compile it again, everything should be okay.

After completed, remember there will be a folder name ‘.libs’ generated under your source tree folder, this is a HIDDEN folder, everything you need just under it.

$ ./cjpeg testimg.bmp > hello.jpeg

a new compressed jpeg file is generated

$ ./djpeg -bmp testimg.jpg > hello.bmp

a new bmp file is generated

use your imagination to do anything.

Good luck!

Android标记贴

这里记录些经常遇到的有关Android/AOSP/PandaBoard的问题(可能比较小，并且又不知道放哪里的事情)！

1. PandaBoard获取root privilege(adb remount)

/path/to/aosp/out/target/product/panda/root/default.prop

修改设定为ro.secure=0
再次打包镜像，理论上这应该对所有的ROM都管用！
当然我这里是AOSP源码编译然后烧录的，如果只是普通的ROM，想root的话，请参考官方或者网络上的方法！

Java知识脉络

Java知识庞大而复杂，所以有必要标记下自己学过哪些东西，让自己更清楚

Java Language Partition

I 基本数据类型引用类型

String
常量池(Constant Pool)存在于.class文件中，运行时被加载，可以扩充，String.intern()方法就可以扩充常量池

String变量是有长度限制的，最大长度为Integer.MAX_VALUE
但String常量(string literals)的最大长度却不为这么多，参考地这(http://java.sun.com/docs/books/jvms/second_edition/html/ClassFile.doc.html#7963)和这

关于 

String s = new String("hello");

创建几个对象的问题，参见这里

会有字符串对象只在Heap中，但是Constant Pool中不存在对应的字面表示吗？Constant Pool中的内容会不会被GC？

II 常用对象

III

IV

V

VI

VII 一些错误或者异常
java.lang.OutOfMemoryError: Requested array size exceeds VM limit

VIII

Java Virtual Machine Partition

I Feature
Stack based
Symbolic reference
Garbage collection
Explicitly defining the primitive data type
Network byte order

II Class Format
Methods in Java are restricted to 64k
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4309152

III GC
根集合是什么，怎么确定根集合？
HotSpot虚拟机中垃圾对象的扫描是采用的路径搜索方法，从根集合开始没有路径可到达的被认为是垃圾对象，可以回收
根集合包括，栈帧当中

IV Instruction Set
invokeinterface: Invokes an interface method
invokespecial: Invokes an initializer, private method, or superclass method
invokestatic: Invokes static methods
invokevirtual: Invokes instance methods

PS.
update 2012-02-09 写的这个破玩意在草稿箱躺了6个月了，发出来边看，边补充吧。

IO，Network，Protocol等等标记帖

这里都是一些感觉写的好或着写的明白的经典内容

IO
IO – 同步，异步，阻塞，非阻塞 （亡羊补牢篇）
http://blog.csdn.net/historyasamirror/article/details/5778378

HTTP
深入理解HTTP协议（转）
http://www.blogjava.net/zjusuyong/articles/304788.html

TCP
位码即TCP标志位,有6种标示:SYN(synchronous建立联机) ACK(acknowledgement 确认) PSH(push传送) FIN(finish结束) RST(reset重置) URG(urgent紧急)
Sequence number(顺序号码) Acknowledge number(确认号码)

TCP状态表
CLOSED
LISTEN
SYN RCVD
SYN SENT
ESTABLISHED
FIN WAIT 1
FIN WAIT 2
TIME WAIT (双方均已断开)
CLOSING
CLOSE WAIT (被动关闭)收到对方关闭请求，并且已经确认
LAST ACK (被动关闭)等待最后一个关闭确认

建立连接过程
一般情况是服务端执行LISTEN原语进入LISTEN(被动打开)状态
客户端发出CONNECT命令，创建报文段(带SYN)并发送，进入SYN SENT状态
服务端收到一个SYN报文段，给客户端回应ACK同时发送一个SYN，进入SYN RCVD状态
客户端收到SYN+ACK报文段，并发送三次握手的最后一个ACK报文段，进入ESTABLISHED状态
服务端收到确认的ACK报文段，完成三次握手，进入ESTABLISHED状态

关闭连接过程
客户端执行CLOSE原语，创建报文段(带FIN)并发送，进入FIN WAIT 1状态
服务端收到一个FIN报文段，确认客户端的请求并回发一个ACK报文段，进入CLOSE WAIT状态
客户端收到服务端的确认ACK报文段，转移到FIN WAIT 2状态，此时从客户端到服务器方向的连接已经断开
服务端应用得到通告后，执行CLOSE原语，创建报文段(带FIN)并发送，进入LAST ACK状态
客户端收到FIN报文段并确认，进入TIME WAIT状态，此时双方连接均已经断开
但TCP要等待一个2倍报文最大生存时间(2MSL)，确保。。。，到超时时间后，删除记录，进入CLOSED状态
服务端收到最后一个ACK报文段，释放连接，删除记录，进入CLOSED状态

http://www.cs.berkeley.edu/~kfall/EE122/lec23/sld001.htm
Three-way handshake
– A ——> Seq k, SYN ——> B
– A <--- Seq j, ACK k + 1, SYN + ACK <--- B - A ----> Seq k + 1, ACK j + 1, ACK —->

Four-way handshake
– A —- Seq k, ACK j + 1, FIN + ACK —-> B
– A <--- Seq j, ACK k + 1, ACK <--- B - ... sometime later ... - A <--- Seq j, ACK k + 1, FIN + ACK <--- B - A ---> Seq k, ACK j + 1, ACK —>

Wireshark真实抓包数据
三次握手

33	44.679312	192.168.1.102	58.215.40.94	TCP	53902 > smtp [SYN] Seq=0 Win=5840 Len=0 MSS=1460 TSV=3199582 TSER=0 WS=6
34	44.761376	58.215.40.94	192.168.1.102	TCP	smtp > 53902 [SYN, ACK] Seq=0 Ack=1 Win=5792 Len=0 MSS=1440 TSV=1575891196 TSER=3199582 WS=7
35	44.761442	192.168.1.102	58.215.40.94	TCP	53902 > smtp [ACK] Seq=1 Ack=1 Win=5888 Len=0 TSV=3199602 TSER=1575891196

四次分手

181	279.133008	192.168.1.102	58.215.40.94	TCP	59658 > smtp [ACK] Seq=7 Ack=93 Win=5888 Len=0 TSV=3258195 TSER=1576125611
182	279.133545	58.215.40.94	192.168.1.102	TCP	smtp > 59658 [FIN, ACK] Seq=93 Ack=7 Win=5888 Len=0 TSV=1576125611 TSER=3258186
183	279.133630	192.168.1.102	58.215.40.94	TCP	59658 > smtp [FIN, ACK] Seq=7 Ack=94 Win=5888 Len=0 TSV=3258195 TSER=1576125611
186	279.264675	58.215.40.94	192.168.1.102	TCP	smtp > 59658 [ACK] Seq=94 Ack=8 Win=5888 Len=0 TSV=1576125739 TSER=3258195

http://blog.chinaunix.net/space.php?uid=20587912&do=blog&cuid=2201855
http://wenku.baidu.com/view/2fd4a6d126fff705cc170af3.html
OSI 7层协议
物理层
数据链路层
网络层
传输层
会话层
表示层
应用层

TCP 4层协议
网络接口层(ARP,RARP…)
网间层(ICMP,IP)
传输层(TCP,UDP)
应用层(SMTP,HTTP,FTP,DNS)