~quf/computers-are-fast-2020

computers-are-fast-2020/src/14.c -rw-r--r-- 4.0 KiB
6f56515eLukas Himbert Draw the rest of the fine owl. 1 year, 7 months ago
                                                                                
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <inttypes.h>

#ifndef BUCKETSIZE
  #define BUCKETSIZE 50
#endif

typedef struct {
  size_t occupied;
  unsigned long long keys[BUCKETSIZE];
  unsigned long long values[BUCKETSIZE];
} bucket_t;

typedef struct {
  size_t n_buckets;
  bucket_t *buckets;
} hash_table_t;

hash_table_t *ht_init(size_t n_buckets) {
  /* Note: buckets NEEDS to be a power of 2! */
  hash_table_t *table = malloc(sizeof *table);
  table->n_buckets = n_buckets;
  if (table == NULL) {
    fprintf(stderr, "Allocation erorr: %s.\n", strerror(errno));
    fflush(stderr);
    exit(EXIT_FAILURE);
  }
  table->buckets = calloc(n_buckets, sizeof *table->buckets);
  if (table->buckets == NULL) {
    fprintf(stderr, "Allocation erorr: %s.\n", strerror(errno));
    exit(EXIT_FAILURE);
  }
  for (size_t i = 0; i < n_buckets; ++i) {
    table->buckets[i].occupied = 0;
  }
  return table;
}

uint32_t ht_hash(uint64_t x) {
  /* adapted djb2 from http://www.cse.yorku.ca/~oz/hash.html */
  uint32_t h = 5381;
  h = ((h << 5) + h) + (uint32_t) ( x        & 255);
  h = ((h << 5) + h) + (uint32_t) ((x >>  8) & 255);
  h = ((h << 5) + h) + (uint32_t) ((x >> 16) & 255);
  h = ((h << 5) + h) + (uint32_t) ((x >> 24) & 255);
  h = ((h << 5) + h) + (uint32_t) ((x >> 32) & 255);
  h = ((h << 5) + h) + (uint32_t) ((x >> 40) & 255);
  h = ((h << 5) + h) + (uint32_t) ((x >> 48) & 255);
  h = ((h << 5) + h) + (uint32_t) ((x >> 54) & 255);
  return h;
}

void ht_insert(hash_table_t *table, uint64_t key, uint64_t value) {
  size_t bucket_id = ht_hash(key) & (table->n_buckets-1);
  bucket_t *bucket = table->buckets + bucket_id;
  for (size_t i = 0; i < bucket->occupied; ++i) {
    if (bucket->keys[i] == key) {
      bucket->values[i] = value;
      return;
    }
  }
  if (bucket->occupied + 1 >= table->n_buckets) {
    fprintf(stderr, "Error inserting (%"PRIu64", %"PRIu64"): Bucket %zu is already full!\n", key, value, bucket_id);
    exit(EXIT_FAILURE);
  }
  bucket->keys[bucket->occupied] = key;
  bucket->values[bucket->occupied] = value;
  ++bucket->occupied;
}

unsigned long long sum(hash_table_t *table) {
  unsigned long long s = 0;
  for (size_t i = 0; i < table->n_buckets; ++i) {
    for (size_t j = 0; j < table->buckets[i].occupied; ++j) {
      s += table->buckets[i].values[j];
    }
  }
  return s;
}

void part2_ht_insert(hash_table_t *mem, unsigned long long loc, unsigned long long val, unsigned long long floating) {
  if (!floating) {
    ht_insert(mem, (uint64_t) loc, val);
    return;
  }
  int i = 0;
  for (; !(floating & 1); ++i, floating >>= 1);
  floating &= ~1LLU;
  floating <<= i;
  part2_ht_insert(mem, loc,             val, floating);
  part2_ht_insert(mem, loc ^ (1ULL<<i), val, floating);
}


int main(void) {
  hash_table_t *mem1 = ht_init(1<<8);
  hash_table_t *mem2 = ht_init(1<<12);
  char line[50];
  unsigned long long mask = 0, maskmask = 0;
  while (fgets(line, sizeof line, stdin) != NULL) {
    if (strncmp(line, "mask", 4) == 0) {
      /* set mask */
      mask = 0;
      maskmask = 0;
      char *b = line;
      for (; *b && *b != '0' && *b != '1' && *b != 'X'; ++b);
      for (; *b && *b != '\n'; ++b) {
        mask <<= 1;
        maskmask <<= 1;
        if (*b == '0') {
          maskmask |= 1;
        }
        else if (*b == '1') {
          mask |= 1;
          maskmask |= 1;
        }
      }
    }
    else {
      /* memory */
      unsigned long long loc = 0;
      unsigned long long val = 0;
      if (sscanf(line, "mem[%llu] = %llu", &loc, &val) != 2) {
        fprintf(stderr, "input error for line: %s\n", line);
        return EXIT_FAILURE;
      }

      ht_insert(mem1, (uint64_t) loc, (val | (mask & maskmask)) & (mask | ~maskmask));

      unsigned long long floating = (~maskmask) & ((1ULL<<36)-1);
      part2_ht_insert(mem2, loc | mask, val, floating);
    }
  }
  if (ferror(stdin)) {
    fprintf(stderr, "Read error: %s.\n", strerror(errno));
    return EXIT_FAILURE;
  }
  printf("%llu\n", sum(mem1));
  printf("%llu\n", sum(mem2));
  return 0;
}