發表於   |  

less是在Linux平台下經常用來觀看檔案內容的工具，不過當在看code時少了syntax highlighting會比較不好閱讀，若想要在less底下也可以有此效果，那可以裝GNU提供的Source-highlight

GNU Source-highlight

相關資訊可參考

https://www.gnu.org/software/src-highlite/

  • 安裝

使用的平台為ubuntu，安裝時輸入

sudo apt install libsource-highlight-common source-highlight

成功的話應可以在/usr/share/底下看到source-highlight資料夾

  • 使用

參考如下

export LESSOPEN="| /usr/bin/src-hilite-lesspipe.sh %s"
export LESS=' -R '

之後使用less看code時就會有syntax highlighting了

發表於   |  

Question:
Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

找到字串中的子字串中有不重複的字元的最大長度，這邊提供一種方法

使用兩個指標計算長度

先以圖示的方式稍微解說一下概念，首先宣告兩個指標皆指向字串的開頭

接著ptr1指標一次一個字元向右移，一直到指到的字元是之前出現過的字元，下圖藍色區段即為第一個substring長度為5

接著ptr2移動到重覆字元位址後一個位址，找尋下一個沒有重覆字元的substring

此時ptr1前進一個且看到重複的字元，但這會造成ptr2往前面的位址移動，顯然移動後的substring會有重覆字元，因此如果ptr2移動的結果是往前面的位址移動，就不移動

依照這個規則ptr1在移動到下圖位址時會看到重覆字元，因此再找到第二個substring長度為5，ptr2也移動到第一個d後面的位址(剛好也是d)

最終ptr1和ptr2的位址如下圖，而這也是最後一個substring長度為2，因此此例最長的substring長度為5

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
32
33
34
35
36
#define MAX_NUM(x, y)	(((x) >= (y)) ? (x) : (y))

#define ASCAII_CHAR_NUM			128
#define CHAR_UNUSED_FLAG		-1

int lengthOfLongestSubstring(char* s) {
	char *ptr1, *ptr2;
	int char_offset[ASCAII_CHAR_NUM]; //(1)
	int i, max_len = 0;
	int str_len = strlen(s);

	if (str_len == 0)
		return 0;

	for (i = 0; i < ASCAII_CHAR_NUM; i++)
		char_offset[i] = CHAR_UNUSED_FLAG;

	ptr1 = s; //(2)
	ptr2 = ptr1;

	for (i = 0; i < str_len - 1; i++) {
		char_offset[*ptr1] = i;
		ptr1++;
		if (char_offset[*ptr1] != CHAR_UNUSED_FLAG) { //(3)
			if (s + char_offset[*ptr1] >= ptr2) { //(4)			
				max_len = MAX_NUM(max_len, ptr1 - ptr2); //(5)
				ptr2 = s + char_offset[*ptr1];
				ptr2++; //(6)
			}
		}	
	}

	max_len = MAX_NUM(max_len, ptr1 - ptr2 + 1); //(7)
	
	return max_len;
}

(1)紀錄曾經出現過的字元的offset的table，若從未出現過則是-1

(2)ptr1及ptr2接指到字串的頭

(3)如果table不為-1代表曾經出現過此字元

(4)如果ptr2移動之後不會造成往前面的位址移動才作處理

(5)只記錄最大長度的substring，這邊要注意的是ptr1 - ptr2之所以可以等於字元的個數是因為一個字元的大小剛好為1，原本的算式為(ptr1 - ptr2) / sizof(char)，而sizeof(char)恆為1因此在這裡可以省略

(6)ptr2移動到重覆字元位址的後一個

(7)計算最後一個substring是否為最長

放到leet code上執行的結果為18ms，超過86.08%的上傳程式

發表於   |  

Question:
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

此題需了解liked list的操作，另外必須注意carry的處理，這邊使用了三種方式來處理，第一種為利用一般的乘除餘數運算，第二種將乘除餘數運算改為加減運算來加速，第三種建立table將運算轉換成查表方式，利用不需任何的運算來加速

理論上執行時間1 > 2 > 3，不過實際上 1 = 2 > 3，有可能是因為運算量不夠大到讓乘除運算和加減運算的差異顯現出來，不過完全不經過任何運算還是可以小幅度的縮減時間

乘除及餘數運算

從兩個linked list的node0 node相加且取除10的餘數代表結果，取除10的商代表是否有carry，carry需要記錄下來，下一個mode作相加時必須加上去，反覆對下一個node作相同的運算，直到兩個linked list都到結尾(NULL)

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
	unsigned char carry = 0;
	struct ListNode *pCurr_node1, *pCurr_node2, *pCurr_node3;
	struct ListNode *pResult = NULL;
	int sum, val1, val2;

	pCurr_node1 = l1;
	pCurr_node2 = l2;

	while (pCurr_node1 != NULL || pCurr_node2 != NULL) { //(1)
		val1 = (pCurr_node1 == NULL) ? 0 : pCurr_node1->val; //(2)
		val2 = (pCurr_node2 == NULL) ? 0 : pCurr_node2->val;
		sum = val1 + val2 + carry; //(3)

		if (sum >= 10) { //(4)
			carry = 1;
			sum %= 10;
		} else {
			carry = 0;
		}

		if (pResult == NULL) { //(5)
			pResult = (struct ListNode *)malloc(sizeof(*pResult));
			pCurr_node3 = pResult;
			pCurr_node3->val = sum;
			pCurr_node3->next = NULL;
		} else {
			pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
			pCurr_node3 = pCurr_node3->next;
			pCurr_node3->val = sum;
			pCurr_node3->next = NULL;
		}

		pCurr_node1 = (pCurr_node1 == NULL) ? NULL : pCurr_node1->next; //(6)
		pCurr_node2 = (pCurr_node2 == NULL) ? NULL : pCurr_node2->next;
	}

	if (carry != 0) { //(7)
		pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
		pCurr_node3 = pCurr_node3->next;
		pCurr_node3->val = 1;
		pCurr_node3->next = NULL;
	}

	return pResult;
}

(1)必須兩個linked list都指到NULL才算結束

(2)建立兩個local變數來取得兩個node需相加的數字，但若遇到其中一個node先指到NULL，那被拿來相加的值會是0

(3)總和為兩個值相加，需再加上carry，預設為0，若某個node有carry，下一個node就會被加上去

(4)如果總和大於10代表有carry，另外結果需改為除以10的餘數

(5)將運算後的結果放到將回傳的linked list

(6)若指到的node已經是NULL，則不跳到下一個node，因為不存在，跳過去會造成系統crash

(7)如果結束後carry不為0則必須處理

放到leet code上執行的結果為35ms，超過68.34%的上傳程式

錯誤用法

如果有參考其他人寫的範例的時候，可以看到一種寫法如下

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
32
33
34
35
36
37
38
39
40
41
42
43
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
	unsigned char carry = 0;
	struct ListNode *pCurr_node1, *pCurr_node2, *pCurr_node3;
	struct ListNode *pResult = NULL;
	int sum, val1, val2;

	pCurr_node1 = l1;
	pCurr_node2 = l2;

	pResult = (struct ListNode *)malloc(sizeof(*pResult)); //(1)
	pCurr_node3 = pResult;
	pCurr_node3->next = NULL;

	while (pCurr_node1 != NULL || pCurr_node2 != NULL) {
		val1 = (pCurr_node1 == NULL) ? 0 : pCurr_node1->val;
		val2 = (pCurr_node2 == NULL) ? 0 : pCurr_node2->val;
		sum = val1 + val2 + carry;

		if (sum >= 10) {
			carry = 1;
			sum %= 10;
		} else {
			carry = 0;
		}

		pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult)); //(2)
		pCurr_node3 = pCurr_node3->next;
		pCurr_node3->val = sum;
		pCurr_node3->next = NULL;

		pCurr_node1 = (pCurr_node1 == NULL) ? NULL : pCurr_node1->next;
		pCurr_node2 = (pCurr_node2 == NULL) ? NULL : pCurr_node2->next;
	}

	if (carry != 0) {
		pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
		pCurr_node3 = pCurr_node3->next;
		pCurr_node3->val = 1;
		pCurr_node3->next = NULL;
	}

	return pResult->next;
}

主要是將第一個node的malloc拉到最外面，迴圈內的malloc就可以不用作原本的NULL判斷，最後回傳的時候再回傳第二個node的位址即可

這方法看似可以省掉一個判斷條件，但事實上是有問題的，因為回傳的linked list的free工作是交給caller的，如果回傳的是第二個node，那caller在free的時候會遺漏掉第一個node，造成此段記憶體無法再被使用，直到程式結束

如果要使用這種寫法，那必須在function裡就將第一個node給清掉

使用加減運算

就硬體角度而言，加法減法運算會比乘除餘數運算來的快，尤其是在沒有乘法器和除法器的狀況下更加明顯，這邊可以修改的就是取除以10餘數的地方，因為這邊的加總最多不會超過19(9 + 9 + 1(carry))，所以可以改寫成-10就是餘數了

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
	unsigned char carry = 0;
	struct ListNode *pCurr_node1, *pCurr_node2, *pCurr_node3;
	struct ListNode *pResult = NULL;
	int sum, val1, val2;

	pCurr_node1 = l1;
	pCurr_node2 = l2;

	while (pCurr_node1 != NULL || pCurr_node2 != NULL) {
		val1 = (pCurr_node1 == NULL) ? 0 : pCurr_node1->val;
		val2 = (pCurr_node2 == NULL) ? 0 : pCurr_node2->val;
		sum = val1 + val2 + carry;

		if (sum >= 10) {
			carry = 1;
			sum -= 10; //(1)
		} else {
			carry = 0;
		}

		if (pResult == NULL) {
			pResult = (struct ListNode *)malloc(sizeof(*pResult));
			pCurr_node3 = pResult;
			pCurr_node3->val = sum;
			pCurr_node3->next = NULL;
		} else {
			pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
			pCurr_node3 = pCurr_node3->next;
			pCurr_node3->val = sum;
			pCurr_node3->next = NULL;
		}

		pCurr_node1 = (pCurr_node1 == NULL) ? NULL : pCurr_node1->next;
		pCurr_node2 = (pCurr_node2 == NULL) ? NULL : pCurr_node2->next;
	}

	if (carry != 0) {
		pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
		pCurr_node3 = pCurr_node3->next;
		pCurr_node3->val = 1;
		pCurr_node3->next = NULL;
	}

	return pResult;
}

(1)取除以10的餘數改寫成-10，因為此例總合不會超過19

不過執行結果並沒有顯著的增加效率，可能是這不是太複雜且頻繁的運算，不足以顯現出明顯的差距

放到leet code上執行的結果為35ms，超過67.08%的上傳程式

使用Table取代運算

乘除運算改為加減運算在這裡並沒有辦法顯著的增加執行速度，不過我們可以利用建立Table的方式，將所有的運算取代成查表的方式，例如我們想要得到{0, 1, 2} + {0, 1, 2}裡面9種組合的運算結果，就可以建立一個像下面這樣的Table

所以就可以將 1 + 1 = 2 ==> [1][1] = 2, 1 + 2 = 3 ==> [1][2] = 3 …

因此我們針對此題建立一張{0 ~ 9} + {0 ~ 9}的Table，但必須考慮到carry的問題，因此這張Table必須有carry的資訊，但是加總之後有可能必須再加上之前低位的carry，因此需再建立一張 {0 ~ 9} + {0, 1} (carry)，相關資訊的Table，直接看程式的Table會更清楚

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
struct AddTableEle {
	unsigned char carry;
	int sum;
};

struct AddCarryTableEle {
	unsigned char carry;
	int sum;
};
//Table1
const struct AddTableEle AddTable[10][10] = {{{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {0, 9}},
									 	{{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {0, 9}, {1, 0}},
									 	{{0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {0, 9}, {1, 0}, {1, 1}},
									 	{{0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {0, 9}, {1, 0}, {1, 1}, {1, 2}},
									 	{{0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {0, 9}, {1, 0}, {1, 1}, {1, 2}, {1, 3}},
									 	{{0, 5}, {0, 6}, {0, 7}, {0, 8}, {0, 9}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}},
									 	{{0, 6}, {0, 7}, {0, 8}, {0, 9}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}},
									 	{{0, 7}, {0, 8}, {0, 9}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}},
									 	{{0, 8}, {0, 9}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}},
									 	{{0, 9}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}}
										};
//Table2
const struct AddCarryTableEle AddCarryTable[10][2] = {{{0, 0}, {0, 1}},
									 			{{0, 1}, {0, 2}},
									 			{{0, 2}, {0, 3}},
									 			{{0, 3}, {0, 4}},
									 			{{0, 4}, {0, 5}},
									 			{{0, 5}, {0, 6}},
									 			{{0, 6}, {0, 7}},
									 			{{0, 7}, {0, 8}},
									 			{{0, 8}, {0, 9}},
									 			{{0, 9}, {1, 0}}
												};

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
	unsigned char carry = 0, flag;
	struct ListNode *pCurr_node1, *pCurr_node2, *pCurr_node3;
	struct ListNode *pResult = NULL;
	int sum, val1, val2;

	pCurr_node1 = l1;
	pCurr_node2 = l2;

	while (pCurr_node1 != NULL || pCurr_node2 != NULL) {
		val1 = (pCurr_node1 == NULL) ? 0 : pCurr_node1->val;
		val2 = (pCurr_node2 == NULL) ? 0 : pCurr_node2->val;
		sum = AddTable[val1][val2].sum;	//(1)
		sum = AddCarryTable[sum][carry].sum; //(2)
		carry = AddCarryTable[AddTable[val1][val2].sum][carry].carry; //(3)
		carry |= AddTable[val1][val2].carry; //(4)

		if (pResult == NULL) {
			pResult = (struct ListNode *)malloc(sizeof(*pResult));
			pCurr_node3 = pResult;
			pCurr_node3->val = sum;
			pCurr_node3->next = NULL;
		} else {
			pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
			pCurr_node3 = pCurr_node3->next;
			pCurr_node3->val = sum;
			pCurr_node3->next = NULL;
		}

		pCurr_node1 = (pCurr_node1 == NULL) ? NULL : pCurr_node1->next;
		pCurr_node2 = (pCurr_node2 == NULL) ? NULL : pCurr_node2->next;
	}

	if (carry != 0) {
		pCurr_node3->next = (struct ListNode *)malloc(sizeof(*pResult));
		pCurr_node3 = pCurr_node3->next;
		pCurr_node3->val = 1;
		pCurr_node3->next = NULL;
	}

	return pResult;
}

Table1 : 以AddTable[3][5] = {0, 8}為例，代表(3 + 5) % 10 = 8，且carry為0，AddTable[6][6] = {1, 2}為例，代表(6 + 6) % 10 = 2，且carry為1

Table2 : 以AddCarryTable[5][0] = {0, 5}為例，代表經過Table1得到結果為5且加上carry = 0，會得到carry = 0，及(5 + 0) % 10 = 5的結果，以AddCarryTable[9][1] = {1, 0}為例，代表經過Table1得到結果為9且加上carry = 1，會得到carry = 1，及(9 + 1) % 10 = 0的結果

(1)透過Table1得到兩個值相加之後取個位數的值

(2)將經由(1)取到的值透過Table2得到加上先前預算是否有殘留carry後取個位數的值

(3)(4)取得此次的運算是否會產生新的carry

執行結果縮短了約3ms

放到leet code上執行的結果為32ms略低於前面兩種方法，超過84.19%的上傳程式

發表於   |  

Question:
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

此題主要著重在如何有效率的搜尋，這邊使用了三種解法，分別是Brute Force(暴力解)，Binary Search(二分搜尋法)，Hash function(雜湊函數)

假設Hash Function可以達到O(n)的複雜度，那理論上花費時間會是Brute Force > Binary Search > Hash Function，不過實際實驗起來是Brute Force > Binary Search = Hash Function，推測有可能是使用的hash function沒達到O(n)的複雜度，或是LeetCode跑的數據量不足以反應出兩種方式的差距，這部分就不深入探討了

Brute Force

暴力解即是從nums[0]開始往後找是否有數字相加之後可以得到target，如果沒有那就看num[1]接著一樣往後找是否有數字相加之後可以得到target，以此類推，直到找到正確的組合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int* twoSum(int* nums, int numsSize, int target) 
{
	int i, j;
	int *pResult;

	pResult = (int *)malloc(2 * sizeof(int));

	for (i = 0; i < numsSize; i++) {
		for (j = i + 1; j < numsSize; j++) {
			if (*(nums + i) + *(nums + j) == target) {
				*pResult = i;
				*(pResult + 1)= j;
				goto RUN_DONE; 
			}
		}
	}
	RUN_DONE:    
	return pResult;
}

程式就是兩層迴圈，分別兩個兩個相加看是不是要的結果
這裡要注意的是第二層的迴圈在找第二個數字時不用從0開始找，從i+1開始找即可，因為i+1之前的會是已經搜尋過的，例如目前已經搜尋到i = 3那j = 0, 1, 2的狀況分別在之前i = 0 j =3, i = 1 j = 3, i = 2 j = 3時都已經運算過了

放到leet code上執行的結果為89ms，超過74.68%的上傳程式

二分搜尋法可以將搜尋的複雜度降低成O(logn)，不過需先經過排序，排序方式可以使用standard C有支援的qsort

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
int compare(const void *a, const void *b)
{
	return ((*(int *)a - *(int *)b));
}

int binary_search(int *pNums, int size, int val)
{
	int l, u, m;

	l = 0;
	u = size - 1;
	for (;;) {
		if (l > u)
			return -1;
		m = (l + u) >> 1;
		if (*(pNums + m) < val)
			l = m + 1;
		else if (*(pNums + m) == val)
			return m;
		else
			u = m - 1;
    }
}

int* twoSum(int* nums, int numsSize, int target)
{
	int i;
	int offset, val1, val2;
	int *pResult;
	int *pSort_nums;
	int *pCurr_val;
	
	pResult = (int *)malloc(2 * sizeof(int));
	pSort_nums = (int *)malloc(numsSize * sizeof(int));
	memcpy(pSort_nums, nums, sizeof(int) * numsSize);
	//(1)
	qsort(pSort_nums, numsSize, sizeof(int), compare);
	
	pCurr_val = pSort_nums;
	//(2)
	for (i = 0; i < numsSize; i++) {
		val1 = *pCurr_val;
		val2 = target - val1;
		pCurr_val++;
		if (binary_search(pCurr_val, numsSize - i - 1, val2) != -1)
	    	break;
	}
	//(3)
	offset = 0;
	for (i = 0; i < numsSize; i++) {
		if (*(nums + i) == val1 || *(nums + i) == val2) {
			*(pResult + offset) = i;
			if (offset == 1)
				break;
			offset++;
		}
	}

	free(pSort_nums);

	return pResult;
}

(1)首先我們先使用qsort且為由小到大進行排序，因為題目要的答案是數字的位址，而不是數字的值，因此我們不行直接將input的數字串作排序，不然會不知道原本的位址，我們另外令一個一樣大小的陣列，接著memcpy過去，然後將這個陣列作qsort排序

(2)接著一樣找各種配對，不過是使用binary search的方式，而在輸入參數的部分和暴力解一樣，找過的可以不用再找，因此可以看到pCurr_val++且搜尋的大小也可以不斷遞減numsSize - i - 1

(3)最後我們必須從最原始的陣列找出經由binary search找到的兩個數字的位址在哪

放到leet code上執行的結果為3ms明顯低於暴力解方式，超過94.29%的上傳程式

Hash function

Hash function理想狀況可以將複雜度降至趨近於O(n)，這裡使用的是Paul Hsieh的SuperFastHash，相關src code可自行搜尋，不過這邊的程式碼有經過稍微的修改，因為這裡只需要放置integer，因此改成輸入int，且不用輸入size，並且排除掉非4byte倍數長度的情形

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#define HASH_TABLE_NUM 256

unsigned int SuperFastHash (const int val)
{
	unsigned int hash = 0, tmp;
	int rem;
	const char *data = (const char *)&val;

	hash += *(const unsigned short *)data;
	tmp = (*(const unsigned short *)(data + 2) << 11) ^ hash;
	hash = (hash << 16) ^ tmp;
	data += sizeof (unsigned short) << 1;
	hash += hash >> 11;

	/* Force "avalanching" of final 127 bits */
	hash ^= hash << 3;
	hash += hash >> 5;
	hash ^= hash << 4;
	hash += hash >> 17;
	hash ^= hash << 25;
	hash += hash >> 6;

	return hash;
}

int* twoSum(int* nums, int numsSize, int target) 
{
	int i, j, tag = 0;
	int offset, val1, val2;
	int *pResult;
	int (*pHash_table)[HASH_TABLE_NUM];
	int sum[HASH_TABLE_NUM] = {0};
	unsigned int out;
	//(1)
	pResult = (int *)malloc(2 * sizeof(int));
	pHash_table = (int (*)[HASH_TABLE_NUM])malloc(HASH_TABLE_NUM * numsSize * sizeof(int));
	//(2)
	for (i = 0; i < numsSize; i++) {
		out = SuperFastHash(*(const int *)(nums + i));
 		out &= (HASH_TABLE_NUM - 1);
 		(*(pHash_table + sum[out]))[out] = *(nums + i);
		sum[out]++;
	}
	//(3)
	for (i = 0; i < numsSize; i++) {
		val1 = *(nums + i);
		val2 = target - val1;
		out = SuperFastHash((const int)val2);
	 	out &= (HASH_TABLE_NUM - 1);
	 	for (j = 0; j < sum[out]; j++) {
	 		if ((*(pHash_table + j))[out] == val2) {
	 			if (val1 == val2) {
	 				if (tag == 0) {
						tag = 1;
						continue;
					}
				}
				goto RUN_DONE;
			}
		}
	}
	//(4)
RUN_DONE:
	offset = 0;
	for (i = 0; i < numsSize; i++) {
		if (*(nums + i) == val1 || *(nums + i) == val2) {
			*(pResult + offset) = i;
			if (offset == 1)
				break;
			offset++;
		}
	}
	
	free(pHash_table);

	return pResult;
}

(1)pHash_table挖了一塊HASH_TABLE_NUM(256) * numsize的陣列作為hash table使用，使用了256個index來存數字，當然這塊記憶體可能會浪費掉很多空間，不過至少足以保證所有的數字都可以裝的進去，在不考慮記憶體使用空間情況下，可以直接這樣用

(2)接著我們將數字經過hash function運算之後放進hash table裡面，另外使用sum來記錄每個hash table的index裡面放了幾個數字

(3)再來使用hash function來找尋是否有需要的兩個值，這裡要對一個情況作額外的處理，如果有一個target = 6且答案為3+3的狀況，這時我們在hash table找值時必須找到兩次3才算真的符合，因為當你固定其中一個3要去找另外一個3時，會從hash table先找到自己的3，如果找不到另一個3就代表輸入的數列只有一個3

(4)最後從原始的輸入陣列找到兩個值的位址

放到leet code上執行的結果為3ms明顯低於暴力解方式和binary search速度相當，超過94.29%的上傳程式

發表於   |  

一般開發版都會有sample code來協助使用這開發，Atmel也不例外，Sama5d3-Xplained的sample code可以在官方網站下載

http://www.atmel.com/tools/SAMA5D3SOFTWAREPACKAGE.aspx

那要如何放到板子上跑起來呢？
Sama5d3-Xplained有SRAM和DRAM，因此可以將程式放在其中一塊記憶體上跑，不過因為這塊板子的SRAM只有64KB * 2，而DRAM有512MB，因此可以盡量將程式放在DRAM上

建置

我們以./examples/getting-started為例，此例為控制板子上兩顆LED燈，此範例的make file在./examples/getting-started/build/gcc，簡單看一下make file可以看到MEMORIES可選擇sram/ddram，部分範例只能選擇ddram，因為sram的size不夠大，也可以調整TRACE_LEVEL，另外也可以看到CROSS_COMPILE = arm-none-eabi-，這裡目前嘗試無法使用在bootstrap/uboot/kernel上使用的arm-linux-guneabi-，看起來是linker script的問題，推測修正相關command到較新版本即可使用，不過懶得去改linker script，直接用預設的cross compile就好，所以先安裝它吧

sudo apt-get install gcc-arm-none-eabi

接著一般我們第一件事會下make clean，結果也跑出error，因為make file裡的clean使用的是cs-rm，我們直接替換成rm即可成功clean

make clean

要建置出程式就使用

make all

在make file的同層目錄下即可看到bin資料夾，裡面的的兩個bin檔即是需要的執行檔，以sram結尾的就是放到sram，以ddram結尾的則是放到dram

sram

和uboot和bootstrap一樣，需先將NAND CS pin斷開，然後RESET，看見顯示RomBoot後接回NAND CS pin，接著打開smaba tool，在NandFlash頁面選擇Enable NandFlash –> Execute，接著Erase all
–> Execute
因為sram在rom code執行完之後即可使用，不需要額外的初始化，因此直接將程式放在原本bootstrap的位置，rom執行完後即會JMP過來，Send Boot File –> Execute，然後選擇sram結尾的bin檔，之後按RESET，可在uart看到以下訊息

且也可看到板端的兩顆LED分別以不同的頻率閃爍

dram

dram和sram較不一樣的是，dram需透過bootstrap來進行初始化的動作之後才可正常使用，不過這bootstrap需做些特別的設定

bootstrap的建置及下載位址可參考相關連結，這邊只針對設定的部分

首先我們在./at91bootstrap/binaries下

make menuconfig

就可以看到選單畫面，有兩個地方需要設定

1. Image Loading Strategy -> (X)Load 1 MB into start of SDRAM
2. Demo Application Images storage Setup -> (0x20000000) The External Ram Address to Load Demo-App Image

建置完程式之後就可以依照燒bootstrap方式燒到flash，不過要特別注意在使用sma-ba的Send Boot File之前必須先Enable OS PMECC parameters

打開smaba tool，在NandFlash頁面選擇Enable NandFlash –> Execute，Erase all –> Execute，Enable OS PMECC parameters -> Execute，Send Boot File

接著在Address填上0x40000(bootstrap JMP之後的位址)，Sned File Name就選以dram結尾的sample code的bin檔，最後按Send File

成功之後按RESET可在UART看到以下訊息，和sram不同的是多了bootstrap的相關訊息

且也可看到板端的兩顆LED分別以不同的頻率閃爍

發表於   |  

指標及一維陣列

在不少的書籍，我們都可以看到可以把陣列看成指標，這不完全正確，但在實作上也不能說完全不正確

本質上陣列名稱代表的是一個位址，而指標代表的是位址的位址，因此在宣告上是不相等的，例如你在某一個地方宣告了int a[10]，而在其他地方想extern進來，但如果使用的是extern *a，那會compile error，因為位址和位址的位址並不一樣
再來如果a[10]真的和*a是一樣的，那sizeof(a)就會應該是4

那為什麼我們在實際使用上結果會是一樣的呢呢?下面這個例子都會印出20

int a[] = {10, 20, 30};

printf("%d", a[1]);
printf("%d", *(a + 1));

那是因為陣列在compiler階段都會被轉成指標，當看到a[1]的時候就從a的位址加上1個integer的size，如果看到*(a + 1)那行為會一樣
差別只在如果compiler知道a是陣列那會忽略’*’和’&’也就是不會作dereference，這樣也可以解釋為什麼下面這情況compiler認為是合法的

int b[3] = {10, 20, 30};

b[99] = 40;

那在什麼狀況下會完全相等呢?只有在傳陣列參數到函式的時候，以下三種情況compiler編出來會一模一樣，事實上在傳陣列到函式裡面時，真正傳的是指標並不是整份陣列複製過去

func(int *verctor) {...};
func(int verctor[]) {...};
func(int verctor[10]) {...};

試著想一下以下這段程式碼會印出什麼

#include <stdio.h>

char ga[2] = {'a', 'b'};

void func_in_vec(char ca[2])
{
    printf("sizeof ca : %ld \n", sizeof(ca));
    printf("&ca : %p \n", &ca);
    printf("&(ca[0]) : %p \n", &(ca[0]));
     printf("&(ca[1]) : %p \n", &(ca[1]));
     printf("\n");
}

void func_in_ptr(char *pa)
{
     printf("sizeof pa : %ld \n", sizeof(pa));
     printf("&pa : %p \n", &pa);
     printf("&(pa[0]) : %p \n", &(pa[0]));
     printf("&(pa[1]) : %p \n", &(pa[1]));
     printf("\n");
}

int main(void)
{
     printf("sizeof ga : %ld \n", sizeof(ga));
     printf("&ga : %p \n", &ga);
     printf("ga : %p \n", ga);
     printf("&(ga[0]) : %p \n", &(ga[0]));
     printf("&(ga[1]) : %p \n", &(ga[1]));
    printf("\n");

    func_in_vec(ga);
     func_in_ptr(ga);         

    return 0;
}

結果如下(有可能在不同平台會有不同結果，這邊是在x64平台的結果，不過概念是一樣的)

sizeof ga : 2 -------------(1)    
&ga : 0x601048 ------------(2)
ga : 0x601048 -------------(3)
&(ga[0]) : 0x601048 -------(4)
&(ga[1]) : 0x601049 -------(5)

sizeof ca : 8 -------------(6)
&ca : 0x7fffd7b1c718 ------(7)
&(ca[0]) : 0x601048 -------(8)
&(ca[1]) : 0x601049 -------(9)

sizeof pa : 8 -------------(10)
&pa : 0x7fffd7b1c718 ------(11)
&(pa[0]) : 0x601048 -------(12)
&(pa[1]) : 0x601049 -------(13)

由(1)可看出ga的型別為2byte的陣列，代表不直接相等指標
(2)(3)可看出&ga = ga，代表雖然compiler會將陣列轉成指標，但會忽略’*’和’&’，
(6)(8)可看出若經由funtion傳入參數後皆轉為指標，因此取sizeof為8(64位元平台)

指標及二維陣列(矩陣)

在現實生活上我們有二維陣列的概念，用來作運算或儲存各種資料，但是在記憶體裡是如何儲存這些資料?記憶體只是一大塊連續的位址空間，如何實現二維陣列的概念?

事實上在記憶體裡面二維陣列就是陣列的陣列，而三維陣列則是陣列的陣列的陣列，依此類推

舉個例子來說，一個[3][2]的陣列代表的是有一個大小3的陣列裡面有大小2的陣列，共6個，參考下圖即可清楚看出，裡面的數字代表的就是程式取值時需給的二維陣列位址，橘色代表的是第一層陣列，藍色代表第二層陣列(陣列的陣列)

試著想一下以下這段程式碼會印出什麼

int main(void)
{
    int a[3][2] = {{10, 20}, {30, 40}, {50, 60}};
    int *b = a[0];

    printf("a[0][0] = %d\n", a[0][0]);
    printf("a[0][1] = %d\n", a[0][1]);
    printf("a[1][1] = %d\n", a[1][1]);
    printf("a[2][1] = %d\n", a[2][1]);

    printf("*(b + 0) = %d\n", *(b + 0));
     printf("*(b + 1) = %d\n", *(b + 1));
     printf("*(b + 3) = %d\n", *(b + 3));
     printf("*(b + 5) = %d\n", *(b + 5));

     return 0;
}

結果如下

a[0][0] = 10 ---(1)
a[0][1] = 20 ---(2)
a[1][1] = 40 ---(3)
a[2][1] = 60 ---(4)
*(b + 0) = 10 ---(5)
*(b + 1) = 20 ---(6)
*(b + 3) = 40 ---(7)
*(b + 5) = 60 ---(8)

從下圖可看出此段程式將b指向第一層陣列a[0]的位址，搭配下圖和以上的結果可清楚看出(1) = (5)、(2) = (6)、(3) = (7)、(4) = (8)，也可看出記憶體擺放的位址和二維陣列的關係

指標及三維陣列

了解指標與陣列關係之後，我們可以來看更為抽象的三維以上的陣列，事實上如果能轉換成記憶體實際擺放的位址來看，也就不會覺得抽象了，假如有一個a[2][3][4]的三維陣列，那在記憶體擺放的情形如下，橘色代表第一維陣列，藍色代表第二維陣列，綠色代表第三維陣列，
因此此陣列為一個大小為2的陣列裡面有大小為3的陣列裡面有大小為4的陣列，共24個

試著想一下以下這段程式碼會印出什麼

int main(void)
{
    int a[2][3][4] = {0};
    int *b = a[0][0];
    int i, j, k;

     for (i = 0; i < 2; i++)
        for (j = 0; j < 3; j++)
             for (k = 0; k < 4; k++)
                 a[i][j][k] = i + j + k;

     printf("a[0][0][0] = %d\n", a[0][0][0]);
     printf("a[0][0][2] = %d\n", a[0][0][2]);
     printf("a[0][1][1] = %d\n", a[0][1][1]);
     printf("a[0][2][3] = %d\n", a[0][2][3]);
     printf("a[1][0][0] = %d\n", a[1][0][0]);
     printf("a[1][2][2] = %d\n", a[1][2][2]);

     printf("*(b + 0) = %d\n", *(b + 0));
     printf("*(b + 2) = %d\n", *(b + 2));
     printf("*(b + 5) = %d\n", *(b + 5));
     printf("*(b + 11) = %d\n", *(b + 11));
     printf("*(b + 12) = %d\n", *(b + 12));
     printf("*(b + 22) = %d\n", *(b + 22));

     return 0;
}

結果如下

a[0][0][0] = 0
a[0][0][2] = 2
a[0][1][1] = 2
a[0][2][3] = 5
a[1][0][0] = 1
a[1][2][2] = 5
*(b + 0) = 0
*(b + 2) = 2
*(b + 5) = 2
*(b + 11) = 5
*(b + 12) = 1
*(b + 22) = 5

從下圖可看出三維陣列和記憶體的關係，將指標b指到三維陣列的頭，四維以上的陣列和二維三維陣列的原理一樣，可以此類推

接下來我們可以看一下不同type的指標和陣列的關係，首先先看int的指標，試著想一下以下這段程式碼會印出什麼

int main(void)
{
    int a[2][3][4] = {0};
    int *b = a[0][0];
    int *c = a[0][2];
    int *d = a[1][1];
    int i, j, k;
    int cnt = 0;

    for (i = 0; i < 2; i++)
        for (j = 0; j < 3; j++)
            for (k = 0; k < 4; k++) {
                a[i][j][k] = cnt;
                cnt++;
            }

    printf("b = %p, b + 1 = %p\n", b, b + 1);

    printf("*(b + 0) = %d, *(b + 1) = %d\n", *(b + 0), *(b + 1));
    printf("a[0][0][0] = %d, a[0][0][1] = %d\n\n", a[0][0][0], a[0][0][1]);

    printf("*(c + 0) = %d, *(c + 6) = %d\n", *(c + 0), *(c + 6));
    printf("a[0][2][0] = %d, a[1][0][2] = %d\n\n", a[0][2][0], a[1][0][2]);

    printf("*(d + 0) = %d, *(d + 7) = %d\n", *(d + 0), *(d + 7));
    printf("a[1][1][0] = %d, a[1][2][3] = %d\n\n", a[1][1][0], a[1][2][3]);

    return 0;
}

結果如下

b = 0x7fffedac8880, b + 1 = 0x7fffedac8884
*(b + 0) = 0, *(b + 1) = 1
a[0][0][0] = 0, a[0][0][1] = 1

*(c + 0) = 8, *(c + 6) = 14
a[0][2][0] = 8, a[1][0][2] = 14

*(d + 0) = 16, *(d + 7) = 23
a[1][1][0] = 16, a[1][2][3] = 23

b因為指到的是int type，所以b和b+1的差距為4byte

b, c, d皆為指到int的指標，因此可指到此三維陣列的第三維陣列，大小為4(藍色框住的綠色部份)

b指到a[0][0]的大小為4的陣列，因此*(b + 0) = a[0][0][0]，*(b + 1)會加一個int size(4byte)之後取值所以*(b + 1) = a[0][0][1]

c指到a[0][2]的大小為4的陣列，因此*(c + 0) = a[0][2][0]，*(c + 6)會加六個int size(4byte)之後取值所以*(c + 6) = a[1][0][2]

d指到a[1][1]的大小為4的陣列，因此*(d + 0) = a[1][1][0]，*(d + 7)會加七個int size(4byte)之後取值所以*(d + 7) = a[1][2][3]

再來看int[]的指標，試著想一下以下這段程式碼會印出什麼

int main(void)
{
    int a[2][3][4] = {0};
    int (*b)[4] = a[0];
     int (*c)[4] = a[1];
     int i, j, k;
     int cnt = 0;

     for (i = 0; i < 2; i++)
         for (j = 0; j < 3; j++)
             for (k = 0; k < 4; k++) {
                 a[i][j][k] = cnt;
                 cnt++;
             }

     printf("b = %p, b + 1 = %p\n", b, b + 1);

     printf("(*(b + 0))[0] = %d, (*(b + 1))[0] = %d\n", (*(b + 0))[0], (*(b + 1))[0]);
     printf("a[0][0][0] = %d, a[0][0][1] = %d\n\n", a[0][0][0], a[0][1][0]);

     printf("(*(b + 2))[2] = %d, (*(b + 4))[3] = %d\n", (*(b + 2))[2], (*(b + 4))[3]);
     printf("a[0][2][2] = %d, a[1][1][3] = %d\n\n", a[0][2][2], a[1][1][3]);

     printf("(*(c + 1))[1] = %d, (*(c + 2))[2] = %d\n", (*(c + 1))[1], (*(c + 2))[2]);
     printf("a[1][1][1] = %d, a[1][2][2] = %d\n\n", a[1][1][1], a[1][2][2]);    

     return 0;
}

結果如下

b = 0x7fff2c1a96c0, b + 1 = 0x7fff2c1a96d0
(*(b + 0))[0] = 0, (*(b + 1))[0] = 4
a[0][0][0] = 0, a[0][1][0] = 4

(*(b + 2))[2] = 10, (*(b + 4))[3] = 19
a[0][2][2] = 10, a[1][1][3] = 19

(*(c + 1))[1] = 17, (*(c + 2))[2] = 22
a[1][1][1] = 17, a[1][2][2] = 22

b因為是指到int[4]的指標因此b和b+1的差距為16byte(4byte(int) * 4(size))

b, c, d皆為指到int[4]的指標，因此可指到此三維陣列的第二維陣列，大小為3(橘色框住的藍色部份)

b指到a[0]的大小為3的陣列，因此(*(b + 0))[0] = a[0][0][0]，*(b + 1)會加四個int size(16byte)之後取值所以(*(b + 1))[0] = a[0][1][0]，*(b + 2)會加八個int size(32byte)之後取值所以(*(b + 2))[2] = a[0][2][2]，*(b + 4)會加十六個int size(64byte)之後取值所以(*(b + 4))[3] = a[1][1][3]

c指到a[1]的大小為4的陣列，因此(*(c + 1))[1] = a[1][1][1]，*(c + 2)會加八個int size(32byte)之後取值所以(*(c + 2))[2] = a[1][2][2]

再來看int[][]的指標，試著想一下以下這段程式碼會印出什麼

int main(void)
{
    int a[2][3][4] = {0};
     int (*b)[3][4] = a;
     int i, j, k;
     int cnt = 0;

     for (i = 0; i < 2; i++)
         for (j = 0; j < 3; j++)
             for (k = 0; k < 4; k++) {
                 a[i][j][k] = cnt;
                 cnt++;
             }

     printf("b = %p, b + 1 = %p\n", b, b + 1);

     printf("(*(b + 0))[0][0] = %d, (*(b + 0))[0][2] = %d\n", (*(b + 0))[0][0], (*(b + 0))[0][2]);
     printf("a[0][0][0] = %d, a[0][0][2] = %d\n\n", a[0][0][0], a[0][0][2]);
     printf("(*(b + 0))[2][1] = %d, (*(b + 0))[2][3] = %d\n", (*(b + 0))[2][1], (*(b + 0))[2][3]);
     printf("a[0][2][1] = %d, a[0][2][3] = %d\n\n", a[0][2][1], a[0][2][3]);

     printf("(*(b + 1))[0][1] = %d, (*(b + 1))[2][3] = %d\n", (*(b + 1))[0][1], (*(b + 1))[2][3]);
     printf("a[1][0][1] = %d, a[1][2][3] = %d\n\n", a[1][0][1], a[1][2][3]);

     return 0;
}

結果如下

b = 0x7fff1604c440, b + 1 = 0x7fff1604c470
(*(b + 0))[0][0] = 0, (*(b + 0))[0][2] = 2
a[0][0][0] = 0, a[0][0][2] = 2

(*(b + 0))[2][1] = 9, (*(b + 0))[2][3] = 11
a[0][2][1] = 9, a[0][2][3] = 11

(*(b + 1))[0][1] = 13, (*(b + 1))[2][3] = 23
a[1][0][1] = 13, a[1][2][3] = 23

b因為是指到int[3][4]的指標因此b和b+1的差距為48byte(4byte(int) (3 4)(size))

b, c, d皆為指到int[3][4]的指標，因此可指到此三維陣列的第一維陣列，大小為3 * 4(橘色部份)

b指到a的大小為3 4的陣列，因此(\(b + 0))[0][0] = a[0][0][0]，(*(b + 0))[0][2] = a[0][0][2]，(*(b + 0))[2][1] = a[0][2][1]，(*(b + 0))[2][3] = a[0][2][3]，*(b + 1)會加十二個int size(48byte)之後取值所以(*(b + 1))[0][1] = a[1][0][1]，(*(b + 1))[2][3] = a[1][2][3]，

發表於   |  

一般在開發嵌入式系統時會先在主機端作開發，接著在主機端產生代碼後再放到目標板上執行程式，直接在主機端開發會有較好的開發效率
但一般主機端大部分是x86的系統，如果想要產生可以在ARM或是其他硬體架構可以執行的程式碼，就需要cross-compiler等相關工具的幫忙，而toolchain就像一個懶人包，裡面包含了特定硬體架構下要產生程式碼所需要用到的所有工具

我們可以使用Crosstool-ng來得到需要的toolcahin

前置作業

安裝ct-ng需要有以下package才可以安裝及編譯

sudo apt-get install autoconf automake libtool-bin libexpat1-dev libncurses5-dev bison flex patch curl cvs texinfo git bc build-essential subversion gawk python-dev gperf unzip pkg-config wget help2man

不同版本的ct-ng所需的package有可能不完全相同，或是某些package已經停止支援必須使用替代的package，這部分可由印出來的log得知來增加或更新需要的package

下載安裝ct-ng

我們可由github得到相關的檔案

git clone https://github.com/crosstool-ng/crosstool-ng.git
cd crosstool-ng

進入到ct-ng目錄之後即可以開始安裝，初始設定會將安裝路徑設在/usr/local/，也可以安裝在local端(目前所在的路徑)，我們選擇安裝在local端

autoreconf
./configure --enable-local
make
make install

ct-ng即可使用(因為是安裝在local端，所以必須在此路徑下使用)

配置toolchain

在產生toolchain之前，我們必須先配置好我們需要的toolchain，如果想得知ct-ng可支援產生的toolchain可使用./ct-ng list-samples

Sama5d3-Xplained使用的是ARM Cortex-A5的架構，因此直接輸入以下指令

./ct-ng arm-cortexa5-linux-uclibcgnueabihf

也可以客製化的設定需要的功能

./ct-ng menuconfig
  • Toolchain options裡面的Tuples’s alias可以設定使用cross compiler gcc時要下的指令，我們改成arm-linux來取代原本很長的arm-cortexa5-linux-uclibcgnueabihf
  • 打開c-library裡的Add support for IPV6

產生toolchain

輸入指令

./ct-ng build

等後一段不短的時間之後即可在home底下看到x-tools，裡面即是產生出來的toolchain，接著將bin資料夾的路徑export之後即可使用arm-linux-相關指令

export PATH=$PATH:/home/xxx/x-tools/arm-cortexa5-linux-uclibcgnueabihf/bin

可輸入arm-linux-gcc確認是否可正常使用，若不想每次都重新export此bin檔也可將此段指令加入bashrc

vim ~/.bashrc

發表於   |  

對於Sama5d3這塊板子來說，uboot是在bootstrap之後執行的，可視為第三階段的bootloader，uboot使用的非常廣泛，尤其是在Linux的環境下，幾乎是所有開發者的優先選擇
uboot負責配置主要介面以及帶起kernel(也可以從bootstrap帶起kernel，但這不是一般狀況故不在此討論)

前置作業

要build在開發版上跑的程式必須先有cross compiler，而sama5d3是ARM Cortex-A5的CPU，因此用的gcc如下

sudo apt-get install gcc-arm-linux-gnueabi

安裝完cross compiler之後必須下載uboot的src code(當然必須先有git相關指令，這部份請自行安裝)

sudo apt-get git://github.com/linux4sam/u-boot-at91.git

註1: 也可建立完整的toolchain來得到cross-compile gcc

建置程式

因為Sama5d3預設本來就是跑Linux的，因此建置u-boot-at91過程和Linux的bootstrap/uboot基本上沒什麼太大的不同
你可以在抓下來的程式碼當中的configs資料夾內發現許多default configuration files
若要從flash boot輸入以下指令

make mrproper
make sama5d3_xplained_nandflash_defconfig

若要從SD/MMC card boot輸入以下指令

make mrproper
make sama5d3_xplained_mmc_defconfig

另外也可以使用以下指令進行產生客製化的.config檔，細部使用不在此篇敘述

make menuconfig

最後輸入以下指令，會在最上層目錄看到u-boot.bin，將bin檔放置flash當中的u-boot位置即可在bootstrap執行完成後，跳到此段程式執行

make CROSS_COMPILE=arm-linux-gnueabi-

燒錄到nandflash

建置完u-boot之後可看到最上層目錄多出了一個u-boot.bin，即是我們要燒錄到flash的檔案

我們可以到atmel官網下載SAM-BA工具，檔名為SAM-BA 2.16 for Linux，下載完之後解壓縮可得到sam-ba_cdc_linux資料夾，裡面的執行檔(sam-ba or sam-ba_64)即是我們要使用的工具

首先先把NAND chip select(JP5)設為0接著RESET，若從UART看到RomBoot的log代表成功進入sam-ba監控模式，接著必須把JP5再設回1

接下來要啟動sam-ba，正常打開應可看到Select connection有相關資訊，若沒有的話可能是權限問題，可以用sudo開啟此檔案

1
sudo ./sam-ba

開啟後畫面如下，將板子選至at91sama5d3x-xplained後按Connect

將標籤頁選至NandFlash，Scripts選擇Enable NandFlash，之後按Execute，沒看到紅色字代表成功

在燒uboot前需先Enable OS PMECC parameters

接著就可以燒uboot了，先選擇Send File Name開啟要燒的u-boot.bin，接著將Address設為0x40000，最後按Send File，若沒看到紅字代表成功

最後按RESET可以從UART看到log進入到uboot，且最終會停在可輸入指令的狀態(輸入?可顯示可使用的指令)

發表於   |  

vim是套在Linux上非常好用的編輯軟體，但在trace code的能力上卻比不上Windows上的source insight，但我們可以另外安裝套件，讓vim接近於source insight的使用方式

以下使用了ctags + cscope + taglist + nerdtree + srcexpl + trinity來達成此目標

ctags

ctags可以在函式、變數之間自由進行切換，例如某主函式call了funca()，ctags可以直接跳到funca的函式裡面、也可使用在變數上

  • 安裝

第一步先安裝ctags

sudo apt-get install ctags
or
sudo apt-get install exuberant-ctags
  • 使用

進入程式目錄當中，若是多層的目錄則進到最上層的目錄，接著輸入

ctags -R

接著必須讓vim知道tags需要到哪裡找到，先用vim打開vimrc，之後把下面第二段的資訊加進去

vim ~/.vimrc
set tags=./tags,./TAGS,tags;~,TAGS;~

用vim進到.c .h檔之後移到函式或變數上即可使用快捷鍵找到該函式或變數的定義，也可跳回到使用此函式的地方

"跳至該函式或變數定義
Ctrl + ]
"跳回使用此函式或變數處
Ctrl + t

cscope

cscope可以查詢函式或變數在哪些地方被使用過，或是函式當中使用了哪些函式

  • 安裝

第一步先安裝cscope

sudo apt-get install cscope
  • 使用

進入程式目錄當中，若是多層的目錄則進到最上層的目錄，接著輸入

cscope -Rbqk

參數說明如下

  1. R : 將目錄及子目錄底下的所有文件都建立索引
  2. b : 僅建立關聯數據庫，不導入使用者介面
  3. q : 建立cscope.in.out和cscope.po.out，可增快搜尋速度
  4. k : 不搜尋預設會include進來的函式(/usr/include)

進入vim的一般指令模式之後必須將cscope.out加入

:cs add cscope.out

為了避免每次使用都必須重複輸入，因此可將此段加入vimrc裡，讓vim自動執行，另外cscope的官方網站也提供了建議的vimrc設定
http://cscope.sourceforge.net/cscope_maps.vim

我挑了部分較常使用的加入vimrcvim ~/.vimrc，將以下設定加入vimrc，另外建議自行將註解加入

set cscopetag
set csto=0

if filereadable("cscope.out")
   cs add cscope.out   
elseif $CSCOPE_DB != ""
    cs add $CSCOPE_DB
endif
set cscopeverbose

nmap zs :cs find s <C-R>=expand("<cword>")<CR><CR>
nmap zg :cs find g <C-R>=expand("<cword>")<CR><CR>
nmap zc :cs find c <C-R>=expand("<cword>")<CR><CR>
nmap zt :cs find t <C-R>=expand("<cword>")<CR><CR>
nmap ze :cs find e <C-R>=expand("<cword>")<CR><CR>
nmap zf :cs find f <C-R>=expand("<cfile>")<CR><CR>
nmap zi :cs find i ^<C-R>=expand("<cfile>")<CR>$<CR>
nmap zd :cs find d <C-R>=expand("<cword>")<CR><CR>

其中最後的nmap部分為快捷鍵，其中的第一行指的是可使用zs取代在vim裡輸入:cs find s {name}的指令，後面依此類拖
官網給的設定檔快捷鍵為Ctrl+/+s的組合，不過我是用VIM7.4，對於三個以上的組合鍵似乎有使用上的問題，這部分還沒找到解決方式，因此就先用兩個的組合鍵

最後附上各指令的用途

  1. :cs find s {name} : 找出C語言name的符號
  2. :cs find g {name} : 找出name定義的地方
  3. :cs find c {name} : 找出使用name的地方
  4. :cs find t {name} : 找出name的字串
  5. :cs find e {name} : 相當於egrep功能，但速度更佳
  6. :cs find f {name} : 尋找檔案
  7. :cs find i {name} : 尋找include此檔案的檔案
  8. :cs find d {name} : 尋找name裡面使用到的函式

taglist

taglist可在切出一區塊，顯示此檔案裡的macro，global variable，函式等資訊，且會隨著瀏覽到哪個地方便以不同顏色標示

  • 安裝

下載plugin file，下載地址如下，請自行選擇最新版本下載

http://sourceforge.net/projects/vim-taglist/files/vim-taglist

將plugin/taglist.vim複製到~/.vim/plugin/，doc/taglist.txt複製到~/.vim/doc

  • 使用

可在~/.vimrc裡配置相關設定，其他配置選項請參考官網說明

nmap <F8> :TlistToggle<CR><CR>
let Tlist_Show_One_File=1
let Tlist_Exit_OnlyWindow=1
set ut=100
  1. nmap : 將F8設為開啟taglist的快捷鍵
  2. Tlist_Show_One_File : 只顯示當下瀏覽檔案的func，不顯示之前瀏覽的檔案
  3. Tlist_Exit_OnlyWindow : 如果taglist區塊是最後一個，則退出vim
  4. ut=100 : taglist會標示目前在操作哪個function or variable，但更新速度很慢，這裡把更新速度設成100ms

nerdtree

NERD tree可切出一區塊，顯示根目錄開始的檔案結構，且可由list直接跳到選取的檔案

  • 安裝

下載plugin file，下載地址如下，請自行選擇最新版本下載

http://www.vim.org/scripts/script.php?script_id=1658

將plugin/NERD_tree.vim複製到~/.vim/plugin/，doc/NERD_tree.txt複製到~/.vim/doc
剩下的資料夾autoload, lib, nerdtree_plugin, syntax全部複製到~/.vim底下

  • 使用

可在~/.vimrc裡配置相關設定，其他配置選項請參考官網說明

nmap <F9> :NERDTreeFind<CR><CR>
let NERDTreeWinPos=1
  1. nmap : 將F9設為開啟nerdtree的快捷鍵
  2. NERDTreeWinPos : 將nerdtree區塊放在右邊

SrcExpl(Source Explorer)

SrcExpl可以將當下function的定義顯示出來，或是將當下的變數宣告處顯示出來

  • 安裝

使用git下載plugin檔

git clone https://github.com/wesleyche/SrcExpl

將plugin/srcexpl.vim複製到~/.vim/plugin/，doc/srcexpl.txt複製到~/.vim/doc

  • 使用

官方網站有詳細介紹在.vimrc可用的設定，這裡只列出我有用到的設定

nmap <F10> :SrcExplToggle<CR>
let g:SrcExpl_pluginList = [
    \"__Tag_List__",
    \"_NERD_tree_"
    \
]
  1. nmap : 將F10設為開啟srcexpl的快捷鍵
  2. 若有安裝taglist or nerdtree則需輸入

trinity

trinity用來整合taglist, nerdtree, srcexpl，使可以一鍵開啟三個plgin的功能

  • 安裝

使用git下載plugin檔

git clone https://github.com/wesleyche/Trinity

將plugin/trinity.vim複製到~/.vim/plugin/

  • 使用

接著設定vimrc

nmap <F7> :TrinityToggleAll
  1. nmap : 將F7設為一次打開taglist, nerdtree, srcexpl的快捷鍵

一次打開之後，畫面如下

發表於   |  

函式除了可以回傳一般的變數類型外，也可以回傳指標，包含了變數指標、陣列指標、函式指標等等

函式回傳變數指標

函式可以回傳一個變數的位址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int * fun_rt_para(int a)
{
    static int b = 0;
    
    printf("input value : %d\n", a);
    b += a;
    
    return &b;
}

int main(void)
{
    printf("output value : %d\n\n", *fun_rt_para(1));
    printf("output value : %d\n\n", *fun_rt_para(3));
    printf("output value : %d\n\n", *fun_rt_para(5));
    
    return 0;
}

以上程式碼顯示結果如下，函式將b的位址傳回，這裡要注意的是b必須是全域變數或是static變數，因為local變數的生命週期只有在此函式內(local變數一般放在stack或CPU register)，出了這個函式再透過指標位址取值，有可能取到錯誤的值

函式回傳陣列指標

函式也可以回傳陣列指標

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int * fun_rt_arr()
{
    static int a[3] = {1, 2, 3};

    return a;
}

int main(void)
{
    printf("output value : %d\n", *(fun_rt_arr + 0));
    printf("output value : %d\n", *(fun_rt_arr + 1));
    printf("output value : %d\n", *(fun_rt_arr + 2));
    
    return 0;
}

顯示結果如下，不過使用此方式缺點為caller無法從function name得知陣列大小，caller有可能讀取到邊界外的值，甚至破壞到陣列外的資料，此方法在安全性來講並不妥當

若想讓caller看function就可以知道陣列大小，可以使用以下方式，輸出結果和上面的例子相同，但事實上回傳的type不完全相同

上例回傳的type為int *p，指向int的指標
下例回傳的type為int (*p)[3]指向int[3]的指標

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int (* fun_rt_arr())[3]
{
    static int a[3] = {1, 2, 3};

    return &a;
}

int main(void)
{
    printf("output value : %d\n", (*fun_rt_arr())[0]);
    printf("output value : %d\n", (*fun_rt_arr())[1]));
    printf("output value : %d\n", (*fun_rt_arr())[2]);
    
    return 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

int f1(int b)
{
    printf("Enter f1, value = %d\n", b);
    
    return ++b;
}

int f2(int b)
{
    printf("Enter f2, value = %d\n", b);
    
    return b+=2;
}

int (* fun_rt_fun_ptr(int a))(int b)
{
    if (a == 1)
        return f1;
    else
        return f2;
}

int main(void)
{
    printf("output value : %d\n\n", (fun_rt_fun_ptr(1))(10));
    printf("output value : %d\n\n", (fun_rt_fun_ptr(2))(20));
    
    return 0;
}

細部解析函式的宣告，從最內部的fun_rt_fun_ptr開始

int (* fun_rt_fun_ptr(int a))(int b)
  1. (向右看)fun_rt_fun_ptr為輸入int a的函式
  2. (向左看)fun_rt_fun_ptr回傳一指標
  3. (向右看)此指標為函式指標，且為輸入int b的函式
  4. (向左看)此回傳的函式指標回傳值為int

註：對於較複雜的宣告可參考以下文章 http://www.codeproject.com/Articles/7042/How-to-interpret-complex-C-C-declarations

指標函式回傳函式指標

指標函式回傳函式指標和函式回傳函式指標，原理沒什麼太大的不同，只是宣告上會更為複雜些

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
int f1(int b)
{
    printf("Enter f1, value = %d\n", b);
    
    return ++b;
}

int f2(int b)
{
    printf("Enter f2, value = %d\n", b);
    
    return b+=2;
}

int f3(int b)
{
    printf("Enter f3, value = %d\n", b);
    
    return ++b;
}

int f4(int b)
{
    printf("Enter f4, value = %d\n", b);
    
    return b+=2;
}

int (* fun_rt_fun_ptr1(int a))(int b)
{
    if (a == 1)
        return f1;
    else
        return f2;
}

int (* fun_rt_fun_ptr2(int a))(int b)
{
    if (a == 10)
        return f3;
    else
        return f4;
}

int main(void)
{
    int (* (*func_ptr[])(int))(int) = {fun_rt_fun_ptr1, fun_rt_fun_ptr2};
    
    printf("output value : %d\n\n", func_ptr[0](1)(10));
    printf("output value : %d\n\n", func_ptr[0](2)(20));
    printf("output value : %d\n\n", func_ptr[1](10)(30));
    printf("output value : %d\n\n", func_ptr[1](20)(40));
    
    return 0;
}

函式宣告的部分和函式回傳函式指標沒什麼不同，這也是非常正常的，因為所謂的指標函式並不是指函式本身是指標，而是以指標的方式串接此函式，因此要注意的地方是

int (* (*func_ptr[])(int))(int) = {fun_rt_fun_ptr1, fun_rt_fun_ptr2};

除了宣告的型別必須是回傳函式指標的函式之外，還必須有一個儲存函式指標的陣列

printf("output value : %d\n\n", func_ptr[0](1)(10));
printf("output value : %d\n\n", func_ptr[0](2)(20));
printf("output value : %d\n\n", func_ptr[1](10)(30));
printf("output value : %d\n\n", func_ptr[1](20)(40));

以上的行為依序如下

  1. call fun_rt_fun_ptr1帶入參數1，因參數為1進入f1帶入參數10，回傳值為11
  2. call fun_rt_fun_ptr1帶入參數2，因參數為2進入f2帶入參數20，回傳值為22
  3. call fun_rt_fun_ptr2帶入參數10，因參數為10進入f3帶入參數30，回傳值為31
  4. call fun_rt_fun_ptr2帶入參數20，因參數為20進入f4帶入參數40，回傳值為42