/* What a multidimensional array really is — sizes, addresses, and how a
   subscript expression unfolds. */
#include <stdio.h>

int main(void)
{
    int a[3][4] = {
        { 11, 12, 13, 14 },
        { 21, 22, 23, 24 },
        { 31, 32, 33, 34 },
    };

    /* -- (1) what, and how many ------------------------------------ */
    printf("sizeof a       = %2zu  (three rows of four ints)\n", sizeof a);
    printf("sizeof a[0]    = %2zu  (one row = four ints)\n",  sizeof a[0]);
    printf("sizeof a[0][0] = %2zu  (one element)\n\n",        sizeof a[0][0]);

    /* -- (2) memory is one run — row-major -------------------------- */
    printf("as byte offsets from the start:\n");
    const char *base = (const char *)&a[0][0];
    for (int i = 0; i < 3; i++) {
        printf("  row %d:", i);
        for (int j = 0; j < 4; j++)
            printf(" a[%d][%d]=+%02td", i, j, (const char *)&a[i][j] - base);
        printf("\n");
    }
    printf("  the last subscript varies fastest (row-major).\n\n");

    /* -- (3) unfolding a[2][1] by hand ------------------------------ */
    puts("a[2][1], step by step (addresses as byte offsets from a):");
    printf("  a            type int(*)[4],  +%td\n",
           (const char *)a - base);
    printf("  a + 2        step = sizeof(int[4]) = %zu -> +%zu, offset +%td\n",
           sizeof(int[4]), 2 * sizeof(int[4]), (const char *)(a + 2) - base);
    printf("  *(a + 2)     type int[4] -> decays to int*, offset +%td\n",
           (const char *)*(a + 2) - base);
    printf("  *(a+2) + 1   step = sizeof(int) = %zu -> +%zu, offset +%td\n",
           sizeof(int), 1 * sizeof(int), (const char *)(*(a + 2) + 1) - base);
    printf("  *(*(a+2)+1)  value = %d,  a[2][1] = %d  (the same)\n\n",
           *(*(a + 2) + 1), a[2][1]);

    /* -- (4) same address, different types -------------------------- */
    printf("a, a[0], &a[0][0], &a are all the same address (offset 0):\n");
    printf("  a        +%td   (int(*)[4])\n",    (const char *)a - base);
    printf("  a[0]     +%td   (int*)\n",         (const char *)a[0] - base);
    printf("  &a[0][0] +%td   (int*)\n",         (const char *)&a[0][0] - base);
    printf("  &a       +%td   (int(*)[3][4])\n", (const char *)&a - base);
    printf("but one step means a different distance:\n");
    printf("  a + 1        -> +%td bytes (one row)\n",
           (const char *)(a + 1) - (const char *)a);
    printf("  a[0] + 1     -> +%td bytes (one element)\n",
           (const char *)(a[0] + 1) - (const char *)a[0]);
    printf("  &a + 1       -> +%td bytes (the whole array)\n",
           (const char *)(&a + 1) - (const char *)&a);
    return 0;
}

/* Three layouts for passing a 2-D array to a function — and why it is not int**. */
#include <stdio.h>
#include <stdlib.h>

/* (1) Fixed width: the inner dimension stays in the type.
      The three spellings are the same declaration to the compiler. */
static int sum_fixed(int m[3][4])      { int s = 0; for (int i=0;i<3;i++) for (int j=0;j<4;j++) s += m[i][j]; return s; }
/* These two are *exactly the same* declaration (see the text):
       static int sum_fixed(int m[][4]);
       static int sum_fixed(int (*m)[4]);   */

/* (2) VLA parameter (C99): the width arrives at run time — the way for numeric code */
static int sum_vla(size_t rows, size_t cols, const int a[rows][cols])
{
    int s = 0;
    for (size_t i = 0; i < rows; i++)
        for (size_t j = 0; j < cols; j++) s += a[i][j];
    return s;
}

/* (3) An array of row pointers: a different layout — rows may live apart */
static int sum_rows(size_t rows, size_t cols, int *const rowp[rows])
{
    int s = 0;
    for (size_t i = 0; i < rows; i++)
        for (size_t j = 0; j < cols; j++) s += rowp[i][j];
    return s;
}

int main(void)
{
    int a[3][4] = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12} };

    printf("(1) fixed width  sum_fixed(a)      = %d\n", sum_fixed(a));
    printf("(2) VLA param    sum_vla(3,4,a)    = %d\n", sum_vla(3, 4, a));

    /* build an array of row pointers over the same data */
    int *rowp[3] = { a[0], a[1], a[2] };
    printf("(3) row pointers sum_rows(3,4,rowp) = %d\n\n", sum_rows(3, 4, rowp));

    /* see the difference in layout */
    printf("the layouts differ:\n");
    printf("  a      : int[3][4]  — one run of %zu bytes, 0 indirections\n", sizeof a);
    printf("  rowp   : int*[3]    — %zu bytes of pointers + the rows, 1 indirection\n", sizeof rowp);

    /* the cost of swapping rows differs */
    int *tmp = rowp[0]; rowp[0] = rowp[2]; rowp[2] = tmp;  /* only two pointers move */
    printf("\nswap the row pointers and the order changes with the data untouched: ");
    for (size_t j = 0; j < 4; j++) printf("%d ", rowp[0][j]);
    printf("\n  (doing the same on a 2-D array means actually moving 16 bytes)\n");

    /* jagged rows — a layout a 2-D array cannot have */
    int r0[] = { 1 }, r1[] = { 2, 3, 4 };
    int *jag[2] = { r0, r1 };
    size_t len[2] = { 1, 3 };
    printf("\njagged rows: ");
    for (size_t i = 0; i < 2; i++)
        for (size_t j = 0; j < len[i]; j++) printf("%d ", jag[i][j]);
    printf("\n");
    return 0;
}

/* Allocate flat, view as 2-D — the BLAS-style pattern (leading dimension, submatrix). */
#include <stdio.h>
#include <stdlib.h>

/* Leading dimension (lda): the *stride* from one row to the next.
   It may differ from the column count — which is what makes submatrices free. */
#define AT(a, lda, i, j) ((a)[(size_t)(i) * (size_t)(lda) + (size_t)(j)])

static void fill(double *a, size_t lda, size_t rows, size_t cols)
{
    for (size_t i = 0; i < rows; i++)
        for (size_t j = 0; j < cols; j++)
            AT(a, lda, i, j) = (double)(10 * (i + 1) + (j + 1));
}

static void show(const char *tag, const double *a, size_t lda,
                 size_t rows, size_t cols)
{
    printf("%s (lda=%zu):\n", tag, lda);
    for (size_t i = 0; i < rows; i++) {
        printf("  ");
        for (size_t j = 0; j < cols; j++) printf("%5.0f", AT(a, lda, i, j));
        printf("\n");
    }
}

int main(void)
{
    const size_t rows = 4, cols = 5;

    /* one run — check the multiplication for overflow first (chapter 87's habit) */
    size_t n;
    if (__builtin_mul_overflow(rows, cols, &n)) return 1;
    double *m = malloc(n * sizeof *m);
    if (!m) return 1;

    fill(m, cols, rows, cols);
    show("whole 4x5", m, cols, rows, cols);

    /* (1) A 2-D view — memory from malloc has no declared type, so putting
          an array shape on it is the sound direction (see the text). */
    double (*view)[cols] = (double (*)[cols])m;
    printf("\nthrough the view, view[2][3] = %.0f  (flat: m[2*5+3] = %.0f)\n",
           view[2][3], m[2 * 5 + 3]);

    /* (2) A submatrix — pointing, not copying.
          Rows 1..2, columns 1..3: a 2x3 block. The stride stays 5. */
    double *sub = &AT(m, cols, 1, 1);
    printf("\na submatrix is a start plus a stride, not a copy:\n");
    show("  sub 2x3", sub, cols, 2, 3);

    /* write through the submatrix and the original changes — it is a view */
    AT(sub, cols, 0, 0) = -1;
    printf("\nwriting -1 at sub(0,0) changes the original at (1,1):\n");
    show("whole 4x5", m, cols, rows, cols);

    /* (3) Transposition becomes a stride question too — only the reading order changes */
    printf("\nreading transposed (row step 1, column step %zu):\n", cols);
    for (size_t j = 0; j < cols; j++) {
        printf("  ");
        for (size_t i = 0; i < rows; i++) printf("%5.0f", AT(m, cols, i, j));
        printf("\n");
    }

    free(m);
    return 0;
}

/* How a traversal order sweeps memory — we count *access strides*, not time.
   (Timing differs per build, so only deterministic numbers are printed.) */
#include <stdio.h>
#include <stdlib.h>

#define LINE 64            /* the size of one cache line (chapter 11) */

/* Walk the order, take the cache-line number of each access, and count how
   many distinct lines appear and how often it is the same line as last time. */
typedef struct { size_t lines_touched; size_t same_line_hits; } stats;

static stats scan(const double *base, const size_t *order, size_t n)
{
    stats s = { 0, 0 };
    long prev_line = -1;
    unsigned char seen[4096] = {0};
    for (size_t k = 0; k < n; k++) {
        size_t byte = order[k] * sizeof(double);
        size_t line = byte / LINE;
        if (line < sizeof seen && !seen[line]) { seen[line] = 1; s.lines_touched++; }
        if ((long)line == prev_line) s.same_line_hits++;
        prev_line = (long)line;
    }
    (void)base;
    return s;
}

int main(void)
{
    enum { N = 64 };                       /* 64x64 doubles = 32 KiB */
    static double m[N][N];
    for (size_t i = 0; i < N; i++)
        for (size_t j = 0; j < N; j++) m[i][j] = (double)(i * N + j);

    size_t *order = malloc((size_t)N * N * sizeof *order);
    if (!order) return 1;

    /* (1) Row-major order: m[i][j] with j innermost */
    size_t k = 0;
    for (size_t i = 0; i < N; i++)
        for (size_t j = 0; j < N; j++) order[k++] = i * N + j;
    stats row = scan(&m[0][0], order, (size_t)N * N);

    /* (2) Column order (transposed sweep): m[i][j] with i innermost */
    k = 0;
    for (size_t j = 0; j < N; j++)
        for (size_t i = 0; i < N; i++) order[k++] = i * N + j;
    stats col = scan(&m[0][0], order, (size_t)N * N);

    printf("Reading a 64x64 double matrix 4096 times. Cache line %d bytes,\n", LINE);
    printf("so %zu doubles fit in one line.\n\n", (size_t)LINE / sizeof(double));

    printf("%-14s %14s %18s\n", "order", "lines touched", "same line as last");
    printf("%-14s %14zu %18zu\n", "row-major ij", row.lines_touched, row.same_line_hits);
    printf("%-14s %14zu %18zu\n", "column ji", col.lines_touched, col.same_line_hits);

    printf("\nBoth sweeps touch the same number of lines — they read the same data.\n");
    printf("What differs is *continuity*. Row-major settles %zu accesses in the\n",
           row.same_line_hits);
    printf("line already loaded; column order manages %zu. Its step is %zu bytes,\n",
           col.same_line_hits, (size_t)N * sizeof(double));
    printf("so it jumps to a different line every time.\n");

    free(order);
    return 0;
}