Lab 2

Exercise 0: Makefiles

这个 Exercise 要求我们学会使用 Makefile 来编译 C 语言程序

题目给出了一个 makefile

UNAME_S := $(shell uname -s)
CC=gcc
LD=gcc
CFLAGS=-ggdb -Wall -std=c99
LDFLAGS=

ifeq ($(UNAME_S), Darwin)
    MEMCHECK=valgrind --tool=memcheck --leak-check=full --track-origins=yes --dsymutil=yes
endif

ifeq ($(UNAME_S), Linux)
    MEMCHECK=valgrind --tool=memcheck --leak-check=full --track-origins=yes
endif

BIT_OPS_OBJS = bit_ops.o test_bit_ops.o
BIT_OPS_PROG = bit_ops

LFSR_OBJS = lfsr.o test_lfsr.o
LFSR_PROG = lfsr

VECTOR_OBJS=vector.o vector-test.o
VECTOR_PROG=vector-test

BINARIES=$(VECTOR_PROG) $(BIT_OPS_PROG) $(LFSR_PROG)

all: $(BINARIES)

$(BIT_OPS_PROG): $(BIT_OPS_OBJS)
	$(CC) $(CFLAGS) -g -o $(BIT_OPS_PROG) $(BIT_OPS_OBJS) $(LDFLAGS)

$(LFSR_PROG): $(LFSR_OBJS)
	$(CC) $(CFLAGS) -g -o $(LFSR_PROG) $(LFSR_OBJS) $(LDFLAGS)

lfsr.c: lfsr.h
test_lfsr.c: lfsr.h

bit_ops.c: bit_ops.h
test_bit_ops.c: bit_ops.h

.c.o:
	$(CC) -c $(CFLAGS) $<

vector-memcheck: $(VECTOR_PROG)
	$(MEMCHECK) ./$(VECTOR_PROG)

clean:
	-rm -rf core *.o *~ "#"*"#" Makefile.bak $(BINARIES) *.dSYM

vector.c: vector.h
vector-test.c: vector.h

然后给出了 10 个问题

1. Which target is part of a rule that deletes all the compiled programs? 哪个目标是删除所有编译程序的规则的一部分？

clean

2. Which target is part of a rule that makes all the compiled programs? 哪个目标是创建所有编译程序的规则的一部分？

all

3. Which compiler is currently being used?

CC = gcc

4. What C standard are we currently using?

CFLAGS = -ggdb -Wall -std=c99

5. How would we reference a variable “FOO” in a makefile?

$(FOO)

6. What operating system does the term “Darwin” represent?

"Darwin"代表的是 macOS（和 iOS 等苹果操作系统）的底层核心操作系统。

7. What line creates the lfsr program from its object files? (Give its line number.)

$(LFSR_PROG): $(LFSR_OBJS)           # 行号：假设为第 24 行
    $(CC) $(CFLAGS) -g -o $@ $^ $(LDFLAGS)  # 行号：第 25 行（实际编译命令）

Exercise 1: Bit Operations

编写程序完成 get_bit，set_bit，flip_bit

#include <stdio.h>
#include "bit_ops.h"

// Return the nth bit of x.
// Assume 0 <= n <= 31
unsigned get_bit(unsigned x,
                 unsigned n) {
    // YOUR CODE HERE
    return (x >> n) & 1;
    // Returning -1 is a placeholder (it makes
    // no sense, because get_bit only returns 
    // 0 or 1)
    return -1;
}
// Set the nth bit of the value of x to v.
// Assume 0 <= n <= 31, and v is 0 or 1
void set_bit(unsigned * x,
             unsigned n,
             unsigned v) {
    // YOUR CODE HERE
    if (v == 1) 
        *x |= (1 << n);
    else
        *x &= ~(1 << n);
}
// Flip the nth bit of the value of x.
// Assume 0 <= n <= 31
void flip_bit(unsigned * x,
              unsigned n) {
    (*x) ^= (1 << n);
    // YOUR CODE HERE
}

Exercise 2: Linear Feedback Shift Register

这个 Exercise 要求你实现一个线性反馈移位寄存器，这个图好像挂了

根据描述很容易

void lfsr_calculate(uint16_t *reg) {
    /* YOUR CODE HERE */
    int lfsr = *reg;
    uint16_t bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1;
    lfsr = (lfsr >> 1) | (bit << 15);
    *reg = lfsr;
}

Exercise 3: Memory Management

在本 Exercise，程序实现了一个可变数组 vector 的框架，他要求我们阅读代码并回答问题？

为什么 bad_vector_new() 是不好的？

/* Bad example of how to create a new vector */
vector_t *bad_vector_new() {
    /* Create the vector and a pointer to it */
    vector_t *retval, v;
    retval = &v;

    /* Initialize attributes 初始化 */
    retval->size = 1;
    retval->data = malloc(sizeof(int));
    if (retval->data == NULL) {
        allocation_failed();
    }

    retval->data[0] = 0;
    return retval;
}

这里的 retval 指向了一个由栈内存的变量 v 这个变量在函数运行结束后会被自动释放掉

vector_t also_bad_vector_new() {
    /* Create the vector */
    vector_t v;

    /* Initialize attributes */
    v.size = 1;
    v.data = malloc(sizeof(int));
    if (v.data == NULL) {
        allocation_failed();
    }
    v.data[0] = 0;
    return v;
}

also_bad_vector_new 这段代码也不太好的原因是，v.data = malloc(sizeof(int)); 这里申请的内存在堆内存上

然后返回的时候发生了浅拷贝，如果调用者不自己手动释放内存就会导致内存泄漏

然后我们完善 vector.c 和 vector.c

/* Include the system headers we need */
#include <stdlib.h>
#include <stdio.h>

/* Include our header */
#include "vector.h"

/* Define what our struct is */
struct vector_t {
    size_t size;
    int *data;
};

/* Utility function to handle allocation failures. In this
   case we print a message and exit. */
static void allocation_failed() {
    fprintf(stderr, "Out of memory.\n");
    exit(1);
}

/* Bad example of how to create a new vector */
vector_t *bad_vector_new() {
    /* Create the vector and a pointer to it */
    vector_t *retval, v;
    retval = &v;

    /* Initialize attributes 初始化 */
    retval->size = 1;
    retval->data = malloc(sizeof(int));
    if (retval->data == NULL) {
        allocation_failed();
    }

    retval->data[0] = 0;
    return retval;
}

/* Another suboptimal way of creating a vector */
vector_t also_bad_vector_new() {
    /* Create the vector */
    vector_t v;

    /* Initialize attributes */
    v.size = 1;
    v.data = malloc(sizeof(int));
    if (v.data == NULL) {
        allocation_failed();
    }
    v.data[0] = 0;
    return v;
}

/* Create a new vector with a size (length) of 1
   and set its single component to zero... the
   RIGHT WAY */
vector_t *vector_new() {
    /* Declare what this function will return */
    vector_t *retval;

    /* First, we need to allocate memory on the heap for the struct */
    retval = malloc(sizeof (vector_t));

    /* Check our return value to make sure we got memory */
    if (retval == NULL) {
        allocation_failed();
    }

    /* Now we need to initialize our data.
       Since retval->data should be able to dynamically grow,
       what do you need to do? */
    retval->size = 1;
    retval->data = malloc(sizeof(int));

    /* Check the data attribute of our vector to make sure we got memory */
    if (retval->data == NULL) {
        free(retval);				//Why is this line necessary?
        allocation_failed();
    }

    /* Complete the initialization by setting the single component to zero */
    retval->data[0] = 0;

    /* and return... */
    return retval;
}

/* Return the value at the specified location/component "loc" of the vector */
int vector_get(vector_t *v, size_t loc) {

    /* If we are passed a NULL pointer for our vector, complain about it and exit. */
    if(v == NULL) {
        fprintf(stderr, "vector_get: passed a NULL vector.\n");
        abort();
    }

    /* If the requested location is higher than we have allocated, return 0.
     * Otherwise, return what is in the passed location.
     */
    if (loc < v->size) {
        return v->data[loc];
    } else {
        return 0;
    }
}

/* Free up the memory allocated for the passed vector.
   Remember, you need to free up ALL the memory that was allocated. */
void vector_delete(vector_t *v) {
    /* YOUR SOLUTION HERE */
    if (v == NULL) {
        fprintf(stderr, "vector_delete: passed a NULL vector.\n");
        abort();
    }
    /* Free the data array */
    free(v->data);
}

/* Set a value in the vector. If the extra memory allocation fails, call
   allocation_failed(). */
void vector_set(vector_t *v, size_t loc, int value) {
    /* What do you need to do if the location is greater than the size we have
     * allocated?  Remember that unset locations should contain a value of 0.
     */

    if (v == NULL) {
        fprintf(stderr, "vector_set: passed a NULL vector.\n");
        abort();
    }

    if (loc >= v->size) {
        size_t new_size = loc + 1;
        int *new_data = realloc(v->data, new_size * sizeof(int));
        if (new_data == NULL) {
            allocation_failed();
        }
        v->data = new_data;
        for (size_t i = v->size; i < new_size; i++) {
            v->data[i] = 0;
        }
        v->size = new_size;
    }

    v->data[loc] = value;
    /* YOUR SOLUTION HERE */
}

#ifndef CS61C_VECTOR_H_
#define CS61C_VECTOR_H_
/* vector.h originally written by Jeremy Huddleston <jeremyhu@eecs.berkeley.edu> Sp2004
 *
 * So it looks like you've decided to venture into the "other" files of this
 * lab.  Good.  C Header files (the .h extension) are a way of telling other .c
 * files what they can have access to.  You usually include stdlib.h in your
 * C programs, and this process is identical to including this .h file with the
 * one change being:
 *
 * #include "file.h" 
 * versus
 * #include <file.h>
 *	 
 * The difference is that the <> notation is for system header files and the ""
 * is for ones you provide yourself (in your local directory for instance).
 *	 
 * The header file starts off with
 * #ifndef CS61C_VECTOR_H_
 * #define CS61C_VECTOR_H_
 *	 
 * and ends with a final #endif.  This prevents the file from being included
 * more than once which could've possibly resulted in an infinite loop of
 * file inclusions.
 *
 * First, we define the 'vector_t' datatype.  This next line says that a 'vector_t'
 * is the same as a 'struct vector_t'.  So anywhere in the code after this, we
 * can use 'vector_t *' to mean a pointer to a 'struct vector_t' (which is defined in
 * vector.c).  We can get away with doing this even though we don't know what a
 * struct vector is because all struct pointers have the same representation in memory.
 */

#include <sys/types.h>

typedef struct vector_t vector_t;

/*
 *  Next, we provide the prototypes for the functions defined in vector.c.  This
 *  is a way of telling the .c files that #include this header what they will
 *  have access to.
 */

/* Create a new vector */
vector_t *vector_new();

/* Free up the memory allocated for the passed vector */
/* YOUR CODE HERE */
void vector_delete(vector_t *v);

void vector_set(vector_t *v, size_t loc, int value);

/* Return the value in the vector */
int vector_get(vector_t *v, size_t loc);

/* Set a value in the vector */
/* YOUR CODE HERE */

#endif