cs61c-proj1

Project 1: Conway’s Game of Life, in RGB!

cs61c - Great Ideas in Computer Architecture (Machine Structures) proj1 笔记

课程主页：https://inst.eecs.berkeley.edu/~cs61c/fa20/#by-week

个人仓库：https://github.com/2333monster/my-cs61c-proj

Background

img

实现Game of LIfe.

Getting Started

原仓库设置为只读，我下载了源码解压

PPM Format

PPM是一种存储图片的格式

1
2
3
4
5
6
7
8
9
P3
4 5
255
  0   0   0     0   0   0     0   0   0     0   0   0
255 255 255   255 255 255   255 255 255     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

头部第一行 P3 -> 这是一个P3格式的PPM 文件（还有5种格式）

头部第二行 4 5 -> 图片 4 pixels 宽 5 pixels 高

头部第三行 255 -> 描述颜色值的范围 0~255

文件的余下部分是图片的实际像素，每个像素有三个数字描述分别代表红，绿，蓝

使用convert 命令转换.ppm格式到其他标准格式。

The command convert -compress none glider.png glider.ppm can convert a png to a PPM P3 format, albeit with a different spacing convention than the one we will be using in this project. Similarly, the command convert glider.ppm glider.png can be used to convert a ppm back to a png. This can be useful for debugging purposes, and seeing the actual image files

File I/O

以Color存储pixel 的颜色，Image形式存储所有图片

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct Color 
{
	uint8_t R;
	uint8_t G;
	uint8_t B;
} Color;

typedef struct Image
{
	Color **image;
	uint32_t rows;
	uint32_t cols;
} Image;

使用file I/O 管理文件 fopen fclose fscanf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// fopen opens a file pointer to the "diary.txt" file.
// The "r" indicates that the file should be opened in "read mode".
// Other modes are detailed in the documentation linked above.
FILE *fp = fopen("diary.txt", "r");

// fscanf reads the first word and first number from the given file pointer into buf and num, respectively.
// The second argument is a string format, specifying what exactly fscanf should be reading from the file pointer.
// More options can for the string format can be found in the documentation linked above,
// but you may need to Google to figure out how to scan in specific types.
char buf[20];
int num;
fscanf(fp, "%s %d", buf, &num);

// fclose simply closes the file pointer after we're done with it.
// This frees the memory that fopen allocated for the file.
// This is also a necessary step whenever we are writing to a file:
// without closing the pointer, you may lose the last few lines
// you want to write.
fclose(fp);

Part A1

实现见 https://github.com/2333monster/my-cs61c-proj/blob/master/proj1/imageloader.c

readData()

主要关注下分配空间，理清楚malloc()

1
Image *img = (Image*)malloc(sizeof(Image));

这里分配了一个 Image结构体的空间，用于存储图像的信息，包括图像的行数，列数，以及指向像素空间的指针
分配sizeof(struct Image)大小的内存

1
img->image = (Color **)malloc(totpixel*sizeof(Color*));

这里分配了一个指针数组，用于存储Color结构体的指针。

img->image为Color ** 即 img是一个指向指针数组的指针，其中的每个指针指向一个Color对象

Img是一个Color** 类型，指向的对象是包含 totpixel 个 Color* 的指针数组
分配totpixel*sizeof(Color *) 大小的内存

1
2
3
4
for(int i=0; i<totpixel;i++){
    *(img->image+i) = (Color*)malloc(sizeof(Color));`
    ...
}

这里在上一步分配的指针数组中的每一个指针指向的位置，分配了一个Color 结构体的内存

*(img->image + i) 是一个 Color* 类型，所以我们分配了 sizeof(Color) 字节的内存空间，来存储每个像素的颜色数据。

其次fscanf的参数我是根据make imageloader的报错结果修改的，我最开始是认为是3u的就是3位数的unit32，不理解hhu是什么原因。

注：hhu时unit8的读取

WriteData() & Free()

逻辑上很简单，Free()的话，记得倒着释放，不然会找不到之后的地址。

Part A2

完成Steganography，完整见https://github.com/2333monster/my-cs61c-proj/blob/master/proj1/steganography.c

基于隐写术

载体文件（cover file）相对隐秘文件的大小（指数据含量，以比特计）越大，隐藏后者就越加容易。

因为这个原因，数字图像（包含有大量的数据）在互联网和其他传媒上被广泛用于隐藏消息。这种方法使用的广泛程度无从查考。例如：一个24位的位图中的每个像素的三个颜色分量（红，绿和蓝）各使用8个比特来表示。如果我们只考虑蓝色的话，就是说有28种不同的数值来表示深浅不同的蓝色。而像11111111和11111110这两个值所表示的蓝色，人眼几乎无法区分。因此，这个最低有效位就可以用来存储颜色之外的信息，而且在某种程度上几乎是检测不到的。如果对红色和绿色进行同样的操作，就可以在差不多三个像素中存储一个字节的信息。

更正式一点地说，使隐写的信息难以探测的，也就是保证“有效载荷”（需要被隐蔽的信号）对“载体”（即原始的信号）的调制对载体的影响看起来（理想状况下甚至在统计上）可以忽略。这就是说，这种改变应该无法与载体中的噪声加以区别。

隐写术也可以用作电子水印，这里一条消息（往往只是一个标识符）被隐藏到一幅图像中，使得其来源能够被跟踪或校验。但往往隐写术不具有良好的强健性，当图像被稍微修改后，隐入的消息就无法提取校验了。

evaluateOnePixel

1
2
// 根据给定的图片和行列确定该位置像素的颜色，要求不影响原图片，给新的颜色分配空间
Color *evaluateOnePixel(Image *image, int row, int col)

返回值是一个Color *，设置为secret

1
Color * secret = (Color *)malloc(sizeof(Color));

根据原理，确定该位置的颜色

1
2
int LSB = (*p)->B & 1;
secret->B = secret->G = secret->R = LSB*255;

steganography

对每个像素分别调用evaluateOnePixel即可

完成part A2 时最好自己写测试，而不是使用make steganography命令，至少在我这里，这个命令会导致之前编译成功的makeloader.c的fscanf的参数出现问题。

另编译时，应该同时编译steganography.c和makeloader.c，因为#include "makeloader.h" 即

1
gcc -o steganography steganography.c makeloader.c

Part B

完成 The Game of Life 完整代码见https://github.com/2333monster/my-cs61c-proj/blob/master/proj1/gameoflife.c

规则：

  1. 任何一个周围（8个邻居中）有2或3个活细胞的活细胞，在下一代存活
  2. 任何一个周围有3个或者细胞邻居的死细胞，在下一代存活
  3. 所有其他类型的活细胞下一代带死亡，死细胞下一代仍死亡

规则编码

If my state is... alive (1) dead (0)
And the number of alive neighbors is... 8 7 6 5 4 3 2 1 0 8 7 6 5 4 3 2 1 0
Then the next state I will be... 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0
Converting the 18 bits above to a hexadecimal number

0b00 0001 1000 0000 1000

0x1808
这也被称为0x1808 rule, 还有其他的[interesting rule](https://en.wikipedia.org/wiki/Life-like_cellular_automaton#A_selection_of_Life-like_rules) ，修改hexadecimal number 的值即可(0x0 - 0x3FFFF)

evaluateOneCell()

注意：测试的代码中颜色值只有255或0，255表示alive，0表示dead

三通道颜色（红，绿，蓝）要分别判断，即分别R,G,B是否存活，依据周围8个细胞的R,G,B状态 

1
2
3
4
5
6
7
int rx[8] = {-1,-1,-1,0,0,1,1,1};
int cx[8] = {-1,0,1,-1,1,-1,0,1};

···
for(int i=0;i<8;i++){
    int new_row = ring(row+rx[i],image->rows);
    int new_col = ring(col+cx[i],image->cols);

周围8个细胞的位置

1
2
3
4
5
6
7
int idR = 9*isaliveR + aliveNeighbourR;
if(rule & (1<<idR)){
    nextState->R = 255;
}
else{
    nextState->R = 0;
}

根据规则判断细胞是否存活

这样设计的原理如下

int idR = 9*isaliveR + aliveNeighbourR :

首先isaliveR有两种状态0 和 1，9 * isaliveR 是决定状态的位置，注意上面的规则编码表格，每个细胞周围的细胞存活数有9种情况（0~8），使用9 * isaliveR 当isaliveR = 0 时，就处在dead()的范围

，加上aliveNeighbourR即可确定该细胞的状况，比如死亡周围有5个存活细胞。同理isaliveR = 1。

rule & (1 << idR)

1左移idR位，idR = 4 则 1 << 4即 0000 0000 0000 1000，再跟rule取和，0000 0000 0000 1000 与 0001 1000 0000 1000 取和，得0000 0000 0000 1000。显然若结果不为零，则细胞下一代存活

life() & main()

类似于steganography()的结构

Architecture
#cs61c
cs61c-proj1
https://2333monster.github.io/2023/08/05/cs61c-proj1/
作者
John Titor
发布于
2023年8月5日
许可协议