/* 다차원 배열의 실체 — 크기, 주소, 그리고 첨자가 풀리는 과정. */
#include <stdio.h>

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

    /* ── ① 무엇이 몇 개인가 ──────────────────────────────── */
    printf("sizeof a       = %2zu  (3 rows of 4 ints)\n", sizeof a);
    printf("sizeof a[0]    = %2zu  (one row = 4 ints)\n",  sizeof a[0]);
    printf("sizeof a[0][0] = %2zu  (one element)\n\n",        sizeof a[0][0]);

    /* ── ② 기억은 한 덩어리다 — row-major ────────────────── */
    printf("addresses as byte offsets:\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");

    /* ── ③ 첨자식이 풀리는 과정 — a[2][1] 을 손으로 ───────── */
    puts("resolving a[2][1] step by step (addresses are byte offsets from a):");
    printf("  a            type int(*)[4],  +%td\n",
           (const char *)a - base);
    printf("  a + 2        one 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   one 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]);

    /* ── ④ 같은 주소, 다른 타입 ──────────────────────────── */
    printf("a, a[0], &a[0][0] and &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 size for each:\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;
}

/* 2차원 배열을 함수에 넘기는 세 가지 배치 — 그리고 왜 int** 가 아닌가. */
#include <stdio.h>
#include <stdlib.h>

/* ① 폭이 고정된 2차원: 안쪽 차원은 타입에 남는다.
      셋은 컴파일러에게 완전히 같은 선언이다. */
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; }
/* 다음 둘은 위와 *완전히 같은* 선언이다(본문 참조):
       static int sum_fixed(int m[][4]);
       static int sum_fixed(int (*m)[4]);   */

/* ② VLA 매개변수(C99): 폭을 실행 중에 받는다 — 수치 코드의 정공법 */
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;
}

/* ③ 행 포인터의 배열: 배치가 아예 다르다 — 행마다 따로 살 수 있다 */
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("① fixed width    sum_fixed(a)      = %d\n", sum_fixed(a));
    printf("② VLA parameter  sum_vla(3,4,a)    = %d\n", sum_vla(3, 4, a));

    /* 행 포인터 배열을 만들어 같은 자료를 가리키게 한다 */
    int *rowp[3] = { a[0], a[1], a[2] };
    printf("③ row pointers   sum_rows(3,4,rowp) = %d\n\n", sum_rows(3, 4, rowp));

    /* 배치의 차이를 눈으로 */
    printf("the layouts differ:\n");
    printf("  a      : int[3][4]  - one block of %zu bytes, 0 indirections\n", sizeof a);
    printf("  rowp   : int*[3]    - %zu bytes of pointers plus the rows, 1 indirection\n", sizeof rowp);

    /* 행 교환의 비용이 갈린다 */
    int *tmp = rowp[0]; rowp[0] = rowp[2]; rowp[2] = tmp;  /* 포인터 두 개만 바뀐다 */
    printf("\nswapping row pointers leaves the data alone and changes the order: ");
    for (size_t j = 0; j < 4; j++) printf("%d ", rowp[0][j]);
    printf("\n  (doing the same to a 2-D array would really move 16 bytes)\n");

    /* 들쭉날쭉한 행 — 2차원 배열로는 못 하는 배치 */
    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;
}

/* 평탄하게 잡고 2차원으로 보기 — BLAS 계열이 쓰는 무늬(선행 차원, 부분행렬). */
#include <stdio.h>
#include <stdlib.h>

/* 선행 차원(leading dimension, lda): 한 행에서 다음 행까지의 *간격*.
   실제 열 수(cols)와 다를 수 있다 — 부분행렬이 그래서 공짜가 된다. */
#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;

    /* 한 덩어리로 잡는다 — 곱셈부터 넘침을 본다(86장의 감각) */
    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);

    /* ① 2차원 뷰 — malloc 이 준 기억에는 선언된 타입이 없으므로
          여기에 int[..][..] 모양을 씌우는 것이 정공법이다(본문 참조). */
    double (*view)[cols] = (double (*)[cols])m;
    printf("\nthrough the 2-D view view[2][3] = %.0f  (flat, that is m[2*5+3] = %.0f)\n",
           view[2][3], m[2 * 5 + 3]);

    /* ② 부분행렬 — 복사 없이 '가리키기'만 한다.
          행 1..2, 열 1..3 짜리 2x3 블록. 간격(lda)은 원본 그대로 5. */
    double *sub = &AT(m, cols, 1, 1);
    printf("\na submatrix is not a copy - it is a starting point plus a stride:\n");
    show("  sub 2x3", sub, cols, 2, 3);

    /* 부분행렬에 쓰면 원본이 바뀐다 — 뷰이기 때문이다 */
    AT(sub, cols, 0, 0) = -1;
    printf("\nwriting -1 at (0,0) of the submatrix changes (1,1) of the original:\n");
    show("whole 4x5", m, cols, rows, cols);

    /* ③ 전치도 간격을 바꾸는 문제로 바뀐다(복사 없이 읽는 순서만 바꾼다) */
    printf("\nreading it transposed (row stride 1, column stride %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;
}

/* 순회 순서가 기억을 어떻게 훑는가 — 시간이 아니라 *접근 간격*을 센다.
   (시간 측정은 빌드마다 달라지므로, 결정적인 수만 인쇄한다.) */
#include <stdio.h>
#include <stdlib.h>

#define LINE 64            /* 캐시 라인 한 줄의 크기(11장) */

/* 훑는 순서대로 만져지는 캐시 라인의 *번호*를 세어, 서로 다른 라인이
   몇 개나 등장하는지와 "직전 접근과 같은 라인인가"를 센다. */
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 double = 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;

    /* ① 행 우선(row-major 그대로): m[i][j] 를 j 안쪽으로 */
    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);

    /* ② 열 우선(전치 순회): m[i][j] 를 i 안쪽으로 */
    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("which holds %zu doubles.\n\n", (size_t)LINE / sizeof(double));

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

    printf("\nboth traversals touch the same number of lines - they read the same data.\n");
    printf("what differs is *locality*. Row-major is served from the previous line %zu times\n",
           row.same_line_hits);
    printf("out of the total, column-major only %zu times. Column-major steps %zu bytes\n",
           col.same_line_hits, (size_t)N * sizeof(double));
    printf("each time, so it jumps to a different line every time.\n");

    free(order);
    return 0;
}