Random bit flip in C

Question

I was creating a simple program to change locations on a grid:

#define R 11
#define C 11
#define N 3

typedef struct {
    uint8_t live :1;
    uint8_t next :1;
    uint8_t padding :6;
} point;

int main() {
    uint8_t r, c;
    point graph[R][C] = {
        {{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},{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},{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},{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},{0,0,0},{0,0,0},{0,0,0}},
        {{0,0,0},{0,0,0},{0,0,0},{0,0,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,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,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,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,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}},
    };
    for(size_t i = 0; i < N; i++) {
        for(r = 0; r < R; r++) {
            for(c = 0; c < C; c++){
                putchar(0x30 + graph[r][c].live);
                graph[r][c].next ^= (graph[(r-1) % R][c].live | graph[(r+1) % R][c].live | graph[r][(c+1) % C].live | graph[r][(c-1) % C].live);
            }
            putchar(0x0a);
        }
        putchar(0x0a);
        for(r = 0; r < R; r++) {
            for(c = 0; c < C; c++) {
                graph[r][c].live = graph[r][c].next;
            }
        }
    }
    return 0;

}

Instead of outputting the predicted pattern, (I can't seem to display it without making my question have to much code to be submit it), after the second iteration, graph[0][3] is flipped to a 1 when it should remain a 0.

Alex · Accepted Answer · 2020-05-25T23:41:43.203

3

I think the modulo operator % is screwing things up. See Modulo operation with negative numbers.

You are indexing into graph with (r - 1) % R, which will be negative when r is zero.

Since the index is negative, it's likely grabbing values from farther up in the stack, maybe the value of r or c.

I would create a function that performs the modulo you expect (some examples are given in the link above) and use that instead.

You also must cast it to a signed type, as that will prevent the overflow from setting it to 255: mod(((int8_t)r)-1, R). Or declare r and c as signed types.

edited May 25 '20 at 23:41

answered May 25 '20 at 21:53

Alex

947
6
16

The answers in the linked article did not seem to solve the issue on my machine. I'll try with different sized and signed integers, but this does make sense as a cause for the error. – Shipof123 May 25 '20 at 22:18
@Shipof123 Changing the size or signedness of the integer will not solve the problem. I would use a function like `int mod(int a, int b) { int r = a % b; return r < 0 ? r + b : r; }` Or see the other options in the link. You mentioned these solutions didn't solve the issue? Can you provide some more details? Which did you try? Anyway, in general be careful when using the modulo operator `%` with C. I have definitely fallen victim to similar issues. – Alex May 25 '20 at 22:43
I used `int modulo(int x,int N){ return (x % N + N) %N; }` but I'll switch it over. I think the signedness may effect it, depending on if mod(c-1, N) = mod(255, N) or mod(-1, N) – Shipof123 May 25 '20 at 23:28
I was able to get it to work by casting it to a signed int type `mod(((int8_t)r)-1, R)` – Shipof123 May 25 '20 at 23:36
1

Yes, good catch. The original code has overflow. Typically, I would declare `r` and `c` as `int` right in each of the for loops. Any reason you predeclared them? – Alex May 25 '20 at 23:44
Fixing that now. Origianly I was going to run the program on a 256 x 256 graph and that way r-1 would always equal some value between 0-256. I will be doing that, but using size_t – Shipof123 May 25 '20 at 23:48

Random bit flip in C

1 Answers1