## 4. Generation

The first major step in Kuf is writing a routine that randomly generates a square that will always be technically correct. Before we go through an algorithm for that, a few operations need to be defined.

### 4.1. Being Technically Correct

In Kuf, a technically correct pattern square is one whose quads and subquads do not contain the patterns 0, 6, 9, or f. A quad can be checked with `kuf_quad_check`

<<funcdefs>>=
``int kuf_quad_check(uint8_t quad);``
<<funcs>>=
``````int kuf_quad_check(uint8_t quad)
{

return
}``````

### 4.2. Kuf Random Number Generator

To keep generated output consistent between platforms, a simple 32-bit internal PRNG is implemented, requiring a single 32-bit integer to keep track of state.

<<funcdefs>>=
``uint32_t kuf_rand(uint32_t rng);``
<<funcs>>=
``````uint32_t kuf_rand(uint32_t rng)
{
rng = (1103515245 * rng + 12345) % 2147483648;
return rng;
}``````

`kuf_rng` will call `kuf_rand` and update the state in one call.

<<funcdefs>>=
``uint32_t kuf_rng(uint32_t *rng);``
<<funcs>>=
``````uint32_t kuf_rng(uint32_t *rng)
{
*rng = kuf_rand(*rng);
return *rng;
}``````

### 4.3. Quad Generation + Operations

#### 4.3.1. Set Bit

This static function is used to set a bit in a quad.

<<static_funcdefs>>=
``````static uint8_t set_bit(uint8_t quad,
uint8_t pos,
uint8_t bit);``````
<<funcs>>=
``````static uint8_t set_bit(uint8_t quad,
uint8_t pos,
uint8_t bit)
{
if (bit) quad |= 1 << pos;
else quad &= ~(1 << pos);

}
``````

A randomly generated quad can be generated with `kuf_gen_quad`. This can be any quad pattern, as long as it isn't one of the violation patterns.

<<funcdefs>>=
``uint8_t kuf_gen_quad(uint32_t *rng);``
<<funcs>>=
``````uint8_t kuf_gen_quad(uint32_t *rng)
{

quad = (kuf_rng(rng) >> 8) & 0xf;

}``````

#### 4.3.3. Generate a Tile

A randomly generated tile can be generated with `kuf_gen_tile`. It will return a 1 or a 0.

<<funcdefs>>=
``uint8_t kuf_gen_tile(uint32_t *rng);``

Get the last bit in the RNG.

<<funcs>>=
``````uint8_t kuf_gen_tile(uint32_t *rng)
{
return (kuf_rng(rng) >> 8) & 1;
}``````

#### 4.3.4. Generate a Pair

A randomly generated pair can be generated with `kuf_gen_pair`. It will store the output in the first 2 bits.

<<funcdefs>>=
``uint8_t kuf_gen_pair(uint32_t *rng);``
<<funcs>>=
``````uint8_t kuf_gen_pair(uint32_t *rng)
{
return (kuf_rng(rng) >> 8) & 0x3;
}``````

Pairs can be set to a quad on one of four cardinal sides with `kuf_quad_side_set`, and retrieved with `kuf_quad_side_get`. This takes in a quad and one of the sides `KUF_NORTH`, `KUF_SOUTH`, `KUF_EAST`, and `KUF_WEST`.

<<funcdefs>>=
``````uint8_t kuf_quad_side_set(uint8_t quad,
uint8_t side,
uint8_t pair);
<<funcs>>=
``````uint8_t kuf_quad_side_set(uint8_t quad,
uint8_t side,
uint8_t pair)
{
pair &= 0x3;

switch (side) {
case KUF_NORTH:
break;
case KUF_SOUTH:
break;
case KUF_EAST:
break;
case KUF_WEST:
break;
}

}``````
<<funcs>>=
``````uint8_t kuf_quad_side_get(uint8_t quad, uint8_t side)
{
uint8_t s;

s = 0;

switch (side) {
case KUF_NORTH:
break;
case KUF_SOUTH:
s = (quad >> 2) & 3;
break;
case KUF_EAST:
s = ((quad >> 1) & 1) | (((quad >> 3) & 1) << 1);
break;
case KUF_WEST:
s = (quad & 1) | (((quad >> 2) & 1) << 1);
break;
}

return s;
}``````
<<enums>>=
``````enum {
KUF_NORTH,
KUF_SOUTH,
KUF_EAST,
KUF_WEST
};``````

Tiles in a Quad can be set with `kuf_quad_tile_set` and `kuf_quad_tile_get`. These take in the quad and the intercardinal directions `KUF_NORTHWEST`, `KUF_NORTHEAST`, `KUF_SOUTHWEST`, and `KUF_SOUTHEAST`.

<<funcdefs>>=
``````uint8_t kuf_quad_tile_get(uint8_t quad, uint8_t corner);
uint8_t corner,
uint8_t tile);``````
<<funcs>>=
``````uint8_t kuf_quad_tile_get(uint8_t quad, uint8_t corner)
{
int pos;

pos = 0;

switch (corner) {
case KUF_NORTHWEST:
pos = 0;
break;
case KUF_NORTHEAST:
pos = 1;
break;
case KUF_SOUTHWEST:
pos = 2;
break;
case KUF_SOUTHEAST:
pos = 3;
break;
}

return (quad >> pos) & 1;
}``````
<<funcs>>=
``````uint8_t kuf_quad_tile_set(uint8_t quad,
uint8_t corner,
uint8_t tile)
{
int pos;

pos = 0;

switch (corner) {
case KUF_NORTHWEST:
pos = 0;
break;
case KUF_NORTHEAST:
pos = 1;
break;
case KUF_SOUTHWEST:
pos = 2;
break;
case KUF_SOUTHEAST:
pos = 3;
break;
}

return set_bit(quad, pos, tile & 1);
}``````
<<enums>>=
``````enum {
KUF_NORTHWEST,
KUF_NORTHEAST,
KUF_SOUTHWEST,
KUF_SOUTHEAST
};``````

#### 4.3.7. Manipulate Quads From Squares

Quads in a square can be set and retrieved with `kuf_square_quad_get` and `kuf_square_quad_set`. In addition to the square, can take in a main quad like `KUF_QUAD_A`, `KUF_QUAD_B`, `KUF_QUAD_C`, or `KUF_QUAD_D`, or one of the subquads `KUF_QUAD_AB`, `KUF_QUAD_AC`, `KUF_QUAD_BD`, `KUF_QUAD_CD`, and `KUF_QUAD_ABCD`.

<<funcdefs>>=
``````uint8_t kuf_square_quad_get(uint16_t s, uint8_t pos);
uint8_t pos,
<<funcs>>=
``````uint8_t kuf_square_quad_get(uint16_t s, uint8_t pos)
{

switch (pos) {
}

}

uint8_t pos,
{
switch (pos) {
}
return s;
}``````

Quads A, B, C, and D are stored as nibbles in the 16-bit integer. These can be retrieved by masking at each 4-bit boundary.

``````case KUF_QUAD_A:
break;
quad = (s >> 4) & 0xf;
break;
quad = (s >> 8) & 0xf;
break;
quad = (s >> 12) & 0xf;
break;``````
``````case KUF_QUAD_A:
s = (s & ~0xf) | quad;
break;
s = (s & ~(0xf << 4)) | (quad << 4);
break;
s = (s & ~(0xf << 8)) | (quad << 8);
break;
s = (s & ~(0xf << 12)) | (quad << 12);
break;``````

Quads AB, AC, BD, and CD get a little more challenging because they are contiguously living next to eachother in the integer they are stored in. Some "sewing" needs to happen using the previously defined quad side operations.

For AB, the east side of A becomes the west side, and the west side of B becomes the east side.

``````case KUF_QUAD_AB: {
uint8_t tmp;

/* east side of quad A */
tmp = kuf_quad_side_get(s & 0xf, KUF_EAST);

/* west side of quad B */
tmp = kuf_quad_side_get((s >> 4) & 0xf, KUF_WEST);
break;
}``````
``````case KUF_QUAD_AB: {
uint8_t tmp;

KUF_EAST,
s = (s & ~0xf) | tmp;

tmp = kuf_quad_side_set((s >> 4) & 0xf,
KUF_WEST,
s = (s & ~(0xf << 4)) | (tmp << 4);
break;
}``````

For AC, the south side of A becomes the north side, and the north side of C becomes the south side.

``````case KUF_QUAD_AC: {
uint8_t tmp;

/* south side of quad A */
tmp = kuf_quad_side_get(s & 0xf, KUF_SOUTH);

/* north side of quad C */
tmp = kuf_quad_side_get((s >> 8) & 0xf, KUF_NORTH);
break;
}``````
``````case KUF_QUAD_AC: {
uint8_t tmp;

KUF_SOUTH,
s = (s & ~0xf) | tmp;

tmp = kuf_quad_side_set((s >> 8) & 0xf,
KUF_NORTH,
s = (s & ~(0xf << 8)) | (tmp << 8);
break;
}``````

For BD, the south side of B becomes the north side, and the north side of D becomes the south side.

``````case KUF_QUAD_BD: {
uint8_t tmp;

/* south side of quad B */
tmp = kuf_quad_side_get((s >> 4) & 0xf, KUF_SOUTH);

/* north side of quad D */
tmp = kuf_quad_side_get((s >> 12) & 0xf, KUF_NORTH);
break;
}``````
``````case KUF_QUAD_BD: {
uint8_t tmp;

tmp = kuf_quad_side_set((s >> 4) & 0xf,
KUF_SOUTH,
s = (s & ~(0xf << 4)) | (tmp << 4);

tmp = kuf_quad_side_set((s >> 12) & 0xf,
KUF_NORTH,
s = (s & ~(0xf << 12)) | (tmp << 12);
break;
}``````

For CD, the east side of C becomes the west side, and the west side of D becomes the east side.

``````case KUF_QUAD_CD: {
uint8_t tmp;

/* east side of quad C */
tmp = kuf_quad_side_get((s >> 8) & 0xf, KUF_EAST);

/* west side of quad D */
tmp = kuf_quad_side_get((s >> 12) & 0xf, KUF_WEST);
break;
}``````
``````case KUF_QUAD_CD: {
uint8_t tmp;

tmp = kuf_quad_side_set((s >> 8) & 0xf,
KUF_EAST,
s = (s & ~(0xf << 8)) | (tmp << 8);

tmp = kuf_quad_side_set((s >> 12) & 0xf,
KUF_WEST,
s = (s & ~(0xf << 12)) | (tmp << 12);
break;
}``````

The center quad, ABCD, is composed of a tile from each main quad. Southeast A becomes Northwest. Southwest B becomes Northeast. Northeast C becomes Southwest. Northwest D becomes Southeast.

``````case KUF_QUAD_ABCD: {
uint8_t tmp;

/* A(SE) -> NW */
tmp = kuf_quad_tile_get(s & 0xf, KUF_SOUTHEAST);

/* B(SW) -> NE */
tmp = kuf_quad_tile_get(s >> 4 & 0xf, KUF_SOUTHWEST);

/* C(NE) -> SW */
tmp = kuf_quad_tile_get(s >> 8 & 0xf, KUF_NORTHEAST);

/* D(NW) -> SE */
tmp = kuf_quad_tile_get(s >> 12 & 0xf, KUF_NORTHWEST);

break;
}``````
``````case KUF_QUAD_ABCD: {
uint8_t tmp;

/* Q(NW) -> A(SE) */
KUF_SOUTHEAST,
s = (s & ~0xf) | tmp;

/* Q(NE) -> B(SW) */
tmp = kuf_quad_tile_set((s >> 4) & 0xf,
KUF_SOUTHWEST,

/* Q(SW) -> C(NE) */
s = (s & ~(0xf << 4)) | (tmp << 4);

tmp = kuf_quad_tile_set((s >> 8) & 0xf,
KUF_NORTHEAST,
s = (s & ~(0xf << 8)) | (tmp << 8);

/* Q(SE) -> D(NW) */
tmp = kuf_quad_tile_set((s >> 12) & 0xf,
KUF_NORTHWEST,
s = (s & ~(0xf << 12)) | (tmp << 12);

break;
}``````
<<enums>>=
``````enum {
};``````

### 4.4. Square Generation

With the previously mentioned operations, a technically correct kufic square can be generated. The function to generate a square can be done with `kuf_gen_square`.

<<funcdefs>>=
``uint16_t kuf_gen_square(uint32_t *rng);``
<<funcs>>=
``````uint16_t kuf_gen_square(uint32_t *rng)
{
uint16_t sq;
sq = 0;
<<generate_A>>
<<generate_AC>>
<<generate_C>>
<<generate_ABCD>>
<<generate_BD>>
<<generate_final_tiles>>
return sq;
}``````

A square is created by generating quads and subquads in a specific order, and using the some of the information from previously generated correct quads to generate new correct quads. The order goes A, AC, C, ABCD, BD, AB, BD, B, D.

A gets generated first. This is a random quad.

<<generate_A>>=
``sq = kuf_square_quad_set(sq, KUF_QUAD_A, kuf_gen_quad(rng));``

AC is a constrained subquad whose north pair is the south pair of A. The south pair of AC is generated here. A random pair will be generated. If this quad is valid, it will use it as the AC quad. Otherwise, the procedure will shift through the four other possibilities until it has found a correct quad.

The south pair of AC is set to be the north pair of C.

<<generate_AC>>=
``````{
uint8_t p_s;
uint8_t p_n;
uint8_t ac;

p_s = kuf_gen_pair(rng);
p_n =
KUF_SOUTH);

ac = 0;

int i;

for (i = 0; i < 4; i++) {
ac = kuf_quad_side_set(ac, KUF_SOUTH, (p_s + i) % 4);

}
}

}``````

A similar procedure is used to find the south pair of C.

<<generate_C>>=
``````{
uint8_t p_s;
uint8_t p_n;
uint8_t c;

p_s = kuf_gen_pair(rng);
p_n =
KUF_SOUTH);

c = 0;

int i;

for (i = 0; i < 4; i++) {
c = kuf_quad_side_set(c, KUF_SOUTH, (p_s + i) % 4);

}
}

}``````

At this point, quads A and C have been determined, and these components can be used to generated ABCD. The southeast tile of A and the northeast tile of C together form the west side of ABCD. The east side of ABCD is then generated to complete the quad.

<<generate_ABCD>>=
``````{
uint8_t abcd;
uint8_t p_e;
abcd = 0;

KUF_NORTHWEST,
KUF_SOUTHEAST));

KUF_SOUTHWEST,
KUF_NORTHEAST));

p_e = kuf_gen_pair(rng);

int i;
for (i = 0; i < 4; i++) {
abcd = kuf_quad_side_set(abcd, KUF_EAST, (p_e + i) % 4);
}
}

}``````

From there, things move to the right one tile to generate quad BD. The east side of ABCD is set to be the west side of BD, which in turn is used to fill in the east side and complete the quad.

<<generate_BD>>=
``````{
uint8_t bd;
uint8_t abcd;
uint8_t p_e;

bd = 0;
KUF_WEST,

p_e = kuf_gen_pair(rng);

int i;
for (i = 0; i < 4; i++) {
bd = kuf_quad_side_set(bd, KUF_EAST, (p_e + i) % 4);
}
}

}``````

At this point, only tiles get filled in order to complete the remaining quads. A tile is chosen at random, and if it doesn't work, it goes with the other choice.

The northeast tile of AB gets generated, which then enables the northeast tile of B to be completed.

The southeast tile of CD gets generated, which then enables the southeast tile of D to be completed.

<<generate_final_tiles>>=
``````{
uint8_t ab;
uint8_t cd;
uint8_t b;
uint8_t d;
uint8_t t;

t = kuf_gen_tile(rng);

ab = kuf_quad_tile_set(ab, KUF_NORTHEAST, t ? 0 : 1);
}

t = kuf_gen_tile(rng);

b = kuf_quad_tile_set(b, KUF_NORTHEAST, t ? 0 : 1);
}

t = kuf_gen_tile(rng);

cd = kuf_quad_tile_set(cd, KUF_SOUTHEAST, t ? 0 : 1);
}

t = kuf_gen_tile(rng);

d = kuf_quad_tile_set(d, KUF_SOUTHEAST, t ? 0 : 1);
}

}``````

And with that, a technically correct square is generated.

### 4.5. Building Up Squares From Quads

The function `kuf_glue_square` glues together a square from quads A, B, C, D.

<<funcdefs>>=
``````uint16_t kuf_glue_square(uint8_t a,
uint8_t b,
uint8_t c,
uint8_t d);``````
<<funcs>>=
``````uint16_t kuf_glue_square(uint8_t a,
uint8_t b,
uint8_t c,
uint8_t d)
{
uint16_t s;
s = 0;

return s;
}``````

### 4.6. Breaking Up Squares into Quads

The function `kuf_break_square` will break up a square into core quads A, B, C, D.

<<funcdefs>>=
``````void kuf_break_square(uint16_t s,
uint8_t *a,
uint8_t *b,
uint8_t *c,
uint8_t *d);``````
<<funcs>>=
``````void kuf_break_square(uint16_t s,
uint8_t *a,
uint8_t *b,
uint8_t *c,
uint8_t *d)
{
}``````

### 4.7. Block Generation

Next up is generating a technically correct block. A block is a 2x2 arrangment of squares.

#### 4.7.1. Top Level Function

A block is generated with the function `kuf_gen_block`. The output returns to 4 squares W, X, Y, and Z, which are meant to be arranged left-right, top-bottom in a 2x2 formation.

<<funcdefs>>=
``````void kuf_gen_block(uint32_t *rng,
uint16_t *pw,
uint16_t *px,
uint16_t *py,
uint16_t *pz);``````
<<funcs>>=
``````void kuf_gen_block(uint32_t *rng,
uint16_t *pw,
uint16_t *px,
uint16_t *py,
uint16_t *pz)
{
uint16_t w, x, y, z;
uint16_t wy;
uint16_t wxyz;
uint16_t xz;
uint16_t wx;
uint16_t yz;

w = x = y = z = 0;

<<generate_w>>
<<generate_wy>>
<<generate_y>>
<<generate_wxyz>>
<<generate_xz>>
<<generate_wx>>
<<generate_x>>
<<generate_yz>>
<<generate_z>>

*pw = w;
*px = x;
*py = y;
*pz = z;
}``````

#### 4.7.2. Overview

Making a block is similar to making a square, only one level higher. It begins with a technically correct square, then generating correct squares moving one quad at a time.

Before, some more terminology. Blocks are very similar in concept to squares in that they are both grouped 2x2 units of tiles.

Blocks are composed of 4 squares: moving left right top down, these squares are labelled W, X, Y, Z.

For this block synthesizer algorithm, it is assumed that square W is completed and technically correct. Using W, the algorithm generates a technically correct solution for X, Y, and Z.

Like the how square synthesizer generated intermediate quads, the block solves intermediate squares in the following order: W (provided), WY, Y, WXYZ, XZ, WX, YZ, X, Z.

A bundle of two squares is known as a wall, to distinguish it from sides of a quad.

Squares are generated by solving walls and quads. This algorithm is constricted to top, down, left, right movement. South and east are the only walls required. North east and south east are the only quads required.

#### 4.7.3. Solvers

##### 4.7.3.1. Wall Solver

Generating a wall in a square is known as a "wall solver". For this block algorithm, only an east east and south wall solver required. It works like this: given two quads, generate two new quads that will complete the square.

Wall solvers represent squares as 4 quads A, B, C, and D.

The inputs are the known quads, the outputs are the solved quads.

###### 4.7.3.1.1. Eastern Wall

An eastern solver has knowns A and C, and creates a solution for b and d.

<<funcdefs>>=
``````void kuf_solve_wall_east(uint32_t *rng,
uint8_t a, uint8_t c,
uint8_t *pb, uint8_t *pd);``````
<<funcs>>=
``````void kuf_solve_wall_east(uint32_t *rng,
uint8_t a, uint8_t c,
uint8_t *pb, uint8_t *pd)
{
uint8_t b;
uint8_t d;
uint8_t abcd;
uint8_t bd;
uint8_t ab;
uint8_t cd;

b = 0;
d = 0;

<<eastwall_ABCD_E>>
<<eastwall_BD_E>>
<<eastwall_AB_NE>>
<<eastwall_B_NE>>
<<eastwall_CD_SE>>
<<eastwall_D_SE>>

*pb = b;
*pd = d;
}``````

Solving for the eastern wall is very similar to the approach used in `kuf_gen_square`, except that A and C are already provided. From there the quads are solved in the following order: ABCD, BD, AB, B, CD, D.

To complete ABCD: Southeast A becomes Northwest, and Northeast C becomes Southwest. A new pair is found for the east side to create a technically valid quad.

<<eastwall_ABCD_E>>=
``````{
uint8_t t;
abcd = 0;

t = kuf_gen_pair(rng);

int i;
for (i = 0; i < 4; i++) {
abcd = kuf_quad_side_set(abcd, KUF_EAST, (t + i) % 4);
}
}
}``````

To complete BD: Northeast ABCD becomes Northwest, and Southeast ABCD becomes Southwest. A new pair is found for the east side to create a technically valid quad.

<<eastwall_BD_E>>=
``````{
uint8_t t;
bd = 0;

t = kuf_gen_pair(rng);

int i;
for (i = 0; i < 4; i++) {
bd = kuf_quad_side_set(bd, KUF_EAST, (t + i) % 4);
}
}
}``````

AB is first created from what is known already: the East of A becomes West. The Northeast of ABCD becomes Southeast.

AB is completed by finding the Northeast tile.

<<eastwall_AB_NE>>=
``````{
uint8_t t;

ab = 0;

t = kuf_gen_tile(rng);

ab = kuf_quad_tile_set(ab, KUF_NORTHEAST, t ? 0 : 1);
}
}``````

The known parts of B: East of AB to West, Northeast of BD to Southeast.

B is completed by finding the northeast tile.

<<eastwall_B_NE>>=
``````{
uint8_t t;

b = 0;

t = kuf_gen_tile(rng);

b = kuf_quad_tile_set(b, KUF_NORTHEAST, t ? 0 : 1);
}
}``````

The known parts of CD: South of ABCD becomes north, and Southeast of C becomes Southwest.

CD is completed by finding the southeast tile.

<<eastwall_CD_SE>>=
``````{
uint8_t t;

cd = 0;

t = kuf_gen_tile(rng);

cd = kuf_quad_tile_set(cd, KUF_SOUTHEAST, t ? 0 : 1);
}
}``````

The known parts of D: East of CD becomes West, and Southeast of BD becomes Northeast.

D is completed by finding the southeast tile.

<<eastwall_D_SE>>=
``````{
uint8_t t;

d = 0;

t = kuf_gen_tile(rng);

d = kuf_quad_tile_set(d, KUF_SOUTHEAST, t ? 0 : 1);
}
}``````
###### 4.7.3.1.2. Southern Wall

A southern wall solver has knowns A and B, and creates a solution C and D.

<<funcdefs>>=
``````void kuf_solve_wall_south(uint32_t *rng,
uint8_t a, uint8_t b,
uint8_t *pc, uint8_t *pd);``````

The southern wall uses the same procedure as the eastern wall, just flipped on it's side. The quads are solved in the following order: ABCD, CD, AC, C, BD, D.

<<funcs>>=
``````void kuf_solve_wall_south(uint32_t *rng,
uint8_t a, uint8_t b,
uint8_t *pc, uint8_t *pd)
{
uint8_t c, d;
uint8_t abcd;
uint8_t cd;
uint8_t ac;
uint8_t bd;

c = d = 0;

<<southwall_ABCD_S>>
<<southwall_CD_S>>
<<southwall_AC_SW>>
<<southwall_C_SW>>
<<southwall_BD_SE>>
<<southwall_D_SE>>

*pc = c;
*pd = d;
}``````

Known parts of ABCD: Southeast of A becomes Northwest, and Southwest of B becomes Northeast.

The South side is generated to complete ABCD.

<<southwall_ABCD_S>>=
``````{
uint8_t t;
abcd = 0;

t = kuf_gen_pair(rng);

int i;
for (i = 0; i < 4; i++) {
abcd = kuf_quad_side_set(abcd, KUF_SOUTH, (t + i) % 4);
}
}
}``````

Known parts of CD: Southwest of ABCD becomes Northwest, and Southeast of ABCD becomes Northeast.

The South side is generated to complete CD.

<<southwall_CD_S>>=
``````{
uint8_t t;
cd = 0;

t = kuf_gen_pair(rng);

int i;
for (i = 0; i < 4; i++) {
cd = kuf_quad_side_set(cd, KUF_SOUTH, (t + i) % 4);
}
}
}``````

Known parts of AC: West of ABCD becomes East, and Southwest of A becomes Northwest.

The Southwest tile is generated to complete AC.

<<southwall_AC_SW>>=
``````{
uint8_t t;

ac = 0;

t = kuf_gen_tile(rng);

ac = kuf_quad_tile_set(ac, KUF_SOUTHWEST, t ? 0 : 1);
}
}``````

Known parts of C: South of AC becomes North, and Southwest of CD becomes Southeast.

The Southwest tile is generated to complete C.

<<southwall_C_SW>>=
``````{
uint8_t t;

c = 0;

t = kuf_gen_tile(rng);

c = kuf_quad_tile_set(c, KUF_SOUTHWEST, t ? 0 : 1);
}
}``````

Known parts of BD: East of ABCD becomes West, and Southeast of B becomes Northeast.

The Southeast tile is generated to complete BD.

<<southwall_BD_SE>>=
``````{
uint8_t t;

bd = 0;

t = kuf_gen_tile(rng);

bd = kuf_quad_tile_set(bd, KUF_SOUTHEAST, t ? 0 : 1);
}
}``````

Known parts of D: South of BD becomes North, and Southeast of CD becomes Southwest.

The Southeast tile is generated to complete D.

<<southwall_D_SE>>=
``````{
uint8_t t;

d = 0;

t = kuf_gen_tile(rng);

d = kuf_quad_tile_set(d, KUF_SOUTHEAST, t ? 0 : 1);
}
}``````

Generating a quad in a square is known as a "quad solver". Only southeast and northeast quads need to be implemented. The quad solver works in the following way: given 3 known quads in the square, generate the remaining quad.

<<funcdefs>>=
``````uint8_t kuf_solve_quad_northeast(uint32_t *rng,
uint8_t a,
uint8_t c,
uint8_t d);``````
<<funcs>>=
``````uint8_t kuf_solve_quad_northeast(uint32_t *rng,
uint8_t a,
uint8_t c,
uint8_t d)
{
uint8_t b;
uint8_t abcd;
uint8_t bd;
uint8_t ab;
b = 0;
<<northeast_abcd>>
<<northeast_bd>>
<<northeast_ab>>
<<northeast_b>>
return b;
}``````

It gets solved in the following way:

The known parts of ABCD are created with: Southeast of A to Northwest, Northeast of C to Southwest, and Northwest of D to Southeast.

Complete ABCD by finding the northeast tile.

<<northeast_abcd>>=
``````{
uint8_t t;

abcd = 0;

t = kuf_gen_tile(rng);

abcd = kuf_quad_tile_set(abcd, KUF_NORTHEAST, t ? 0 : 1);
}
}``````

Known BD is comprised of the East of ABCD to West, and the Northeast of D to Southeast.

Complete BD by finding the northeast tile.

<<northeast_bd>>=
``````{
uint8_t t;

bd = 0;

t = kuf_gen_tile(rng);

bd = kuf_quad_tile_set(bd, KUF_NORTHEAST, t ? 0 : 1);
}
}``````

Known AB is comprised of the North of ABCD to South, and the Northeast of A to Northwest.

Complete AB by finding the northeast tile.

<<northeast_ab>>=
``````{
uint8_t t;

ab = 0;

t = kuf_gen_tile(rng);

ab = kuf_quad_tile_set(ab, KUF_NORTHEAST, t ? 0 : 1);
}
}``````

Known B is comprised of the north of BD to South, and the Northeast of AB to Northwest.

Complete B by finding the northeast tile.

<<northeast_b>>=
``````{
uint8_t t;

b = 0;

t = kuf_gen_tile(rng);

b = kuf_quad_tile_set(b, KUF_NORTHEAST, t ? 0 : 1);
}
}``````

<<funcdefs>>=
``````uint8_t kuf_solve_quad_southeast(uint32_t *rng,
uint8_t a,
uint8_t b,
uint8_t c);``````
<<funcs>>=
``````uint8_t kuf_solve_quad_southeast(uint32_t *rng,
uint8_t a,
uint8_t b,
uint8_t c)
{
uint8_t d;
uint8_t abcd;
uint8_t bd;
uint8_t cd;

d = 0;

<<southeast_abcd>>
<<southeast_bd>>
<<southeast_cd>>
<<southeast_d>>

return d;
}``````

Southeast quad is known as D. Like Northeast (B), only finding the southeast tiles.

ABCD is comprised of the southeast of A to northwest, southwest of B to northeast, northeast of C to southwest.

Complete ABCD by finding the southeast tile.

<<southeast_abcd>>=
``````{
uint8_t t;

abcd = 0;

t = kuf_gen_tile(rng);

abcd = kuf_quad_tile_set(abcd, KUF_SOUTHEAST, t ? 0 : 1);
}
}``````

BD is comprised of the east of ABCD to west, and the southeast of B to northeast.

Complete BD by finding the southeast tile.

<<southeast_bd>>=
``````{
uint8_t t;

bd = 0;

t = kuf_gen_tile(rng);

bd = kuf_quad_tile_set(bd, KUF_SOUTHEAST, t ? 0 : 1);
}
}``````

CD is comprised of the south of ABCD to north, and the southeast of C to southwest.

Complete CD by finding the southeast tile.

<<southeast_cd>>=
``````{
uint8_t t;

cd = 0;

t = kuf_gen_tile(rng);

cd = kuf_quad_tile_set(cd, KUF_SOUTHEAST, t ? 0 : 1);
}
}``````

D is comprised of the south of BD to north, and the southeast of CD to southwest.

Complete D by finding the southeast tile.

<<southeast_d>>=
``````{
uint8_t t;

d = 0;

t = kuf_gen_tile(rng);

d = kuf_quad_tile_set(d, KUF_SOUTHEAST, t ? 0 : 1);
}
}``````

#### 4.7.4. The Algorithm

To begin, generate square W. This can be generated entirely with `kuf_gen_square`.

<<generate_w>>=
``w = kuf_gen_square(rng);``

Generate WY. Northern wall of WY (a,b) is the southern wall of W (c,d). This is fed into the southern wall solver to complete WY.

<<generate_wy>>=
``````{
uint8_t a, b, c, d;

c = d = 0;

kuf_solve_wall_south(rng, a, b, &c, &d);

wy = kuf_glue_square(a, b, c, d);
}``````

Generate Y. The Southern wall of WY is fed into the southern wall solver to complete Y.

<<generate_y>>=
``````{
uint8_t a, b, c, d;

c = d = 0;

kuf_solve_wall_south(rng, a, b, &c, &d);

y = kuf_glue_square(a, b, c, d);
}``````

Generate WXYZ. The southeast of W (d) becomes the northwest (a). The northeast of Y (b) becomes the southwest (c). Together they form the Western wall of WXYZ. This is fed into the eastern wall solver to complete WXYZ.

<<generate_wxyz>>=
``````{
uint8_t a, b, c, d;

b = d = 0;

kuf_solve_wall_east(rng, a, c, &b, &d);

wxyz = kuf_glue_square(a, b, c, d);
}``````

Generate XZ. The northeast of WXYZ (b) becomes northwest (a). The southeast (d) of WXYZ becomes southwest (c). This is fed into the east wall solver to complete XZ.

<<generate_xz>>=
``````{
uint8_t a, b, c, d;

b = d = 0;

kuf_solve_wall_east(rng, a, c, &b, &d);

xz = kuf_glue_square(a, b, c, d);
}``````

Generate WX. The East of W (b,d) becomes the West (a, c). The Northeast of WXYZ (b) becomes Southeast (d).

WX is completed using the northeast quad solver.

<<generate_wx>>=
``````{
uint8_t a, b, c, d;

b = kuf_solve_quad_northeast(rng, a, c, d);

wx = kuf_glue_square(a, b, c, d);
}``````

Generate X. The East of WX (b, d) becomes the West (a, c). The Northeast of XZ (b) becomes Southeast (d).

X is completed using the northeast quad solver.

<<generate_x>>=
``````{
uint8_t a, b, c, d;

b = kuf_solve_quad_northeast(rng, a, c, d);

x = kuf_glue_square(a, b, c, d);
}``````

Generate YZ. The East of Y (B, D) becomes West (A, C), and the Southwest of XZ (C) becomes Northeast (B).

The southeast quad of YZ is solved to complete YZ.

<<generate_yz>>=
``````{
uint8_t a, b, c, d;

d = kuf_solve_quad_southeast(rng, a, b, c);

yz = kuf_glue_square(a, b, c, d);
}``````

Generate Z. The East of YZ (B, D) becomes West (A, C), and the Southeast of XZ (D) becomes Northeast (B).

Z is completed using the southeast quad solver.

<<generate_z>>=
``````{
uint8_t a, b, c, d;