All distinct 4x4 patterns

draw-patterns.c

#define STB_IMAGE_WRITE_IMPLEMENTATION
#include "stb_image_write.h"

#define WIDTH_IN_BLOCKS 29
#define HEIGHT_IN_BLOCKS 28

#define PADDING 4

#define BLOCK_WIDTH (4 * 4)
#define BLOCK_HEIGHT (4 * 4)

#define PADDED_BLOCK_WIDTH (BLOCK_WIDTH + PADDING)
#define PADDED_BLOCK_HEIGHT (BLOCK_HEIGHT + PADDING)

#define IMAGE_WIDTH (PADDED_BLOCK_WIDTH * WIDTH_IN_BLOCKS + PADDING)
#define IMAGE_HEIGHT (PADDED_BLOCK_HEIGHT * HEIGHT_IN_BLOCKS + PADDING)

unsigned char output[IMAGE_WIDTH * IMAGE_HEIGHT];

#define SET(x, y) (output[(y)*IMAGE_WIDTH + (x)] = 0xFF)

void draw_pattern(int x, int y, int w, int h, int p) {
  int x1, y1;
  for (y1 = 0; y1 < h; y1++)
    for (x1 = 0; x1 < w; x1++)
      if ((p >> ((y1 % 4) * 4 + (x1 % 4))) & 1)
        SET(x + x1, y + y1);
}

unsigned short patterns[] = {
    0,     1,     3,     5,     7,     15,    18,    19,    20,    21,    22,
    23,    26,    27,    30,    31,    51,    53,    54,    55,    60,    61,
    63,    85,    87,    90,    91,    95,    119,   123,   125,   127,   255,
    260,   261,   262,   263,   266,   267,   270,   271,   278,   279,   282,
    283,   286,   287,   292,   293,   294,   295,   296,   297,   298,   299,
    300,   301,   302,   303,   310,   311,   312,   313,   314,   315,   316,
    317,   318,   319,   325,   326,   327,   330,   331,   334,   335,   340,
    341,   342,   343,   346,   347,   350,   351,   357,   358,   359,   360,
    361,   362,   363,   364,   365,   366,   367,   372,   373,   374,   375,
    376,   377,   378,   379,   380,   381,   382,   383,   417,   419,   420,
    421,   422,   423,   426,   427,   430,   431,   433,   435,   436,   437,
    438,   439,   442,   443,   446,   447,   481,   483,   485,   486,   487,
    490,   491,   494,   495,   497,   498,   499,   500,   501,   502,   503,
    506,   507,   510,   511,   780,   781,   783,   796,   797,   798,   799,
    828,   829,   831,   837,   839,   841,   842,   843,   845,   846,   847,
    854,   855,   857,   858,   859,   860,   861,   862,   863,   869,   871,
    873,   874,   875,   876,   877,   878,   879,   886,   887,   889,   890,
    891,   892,   893,   894,   895,   963,   965,   967,   973,   975,   979,
    981,   982,   983,   986,   987,   989,   990,   991,   1011,  1013,  1014,
    1015,  1020,  1021,  1023,  1285,  1287,  1290,  1291,  1295,  1303,  1306,
    1307,  1310,  1311,  1317,  1319,  1323,  1325,  1327,  1335,  1338,  1339,
    1341,  1342,  1343,  1365,  1367,  1370,  1371,  1375,  1397,  1399,  1402,
    1403,  1405,  1407,  1445,  1447,  1451,  1455,  1461,  1463,  1467,  1470,
    1471,  1525,  1527,  1530,  1531,  1535,  1803,  1805,  1807,  1819,  1821,
    1822,  1823,  1837,  1839,  1851,  1853,  1854,  1855,  1879,  1883,  1885,
    1887,  1911,  1915,  1917,  1919,  1927,  1935,  1943,  1950,  1951,  1959,
    1965,  1967,  1975,  1981,  1982,  1983,  2007,  2015,  2039,  2043,  2045,
    2047,  3855,  3871,  3903,  3935,  3967,  4095,  4382,  4383,  4396,  4397,
    4398,  4399,  4414,  4415,  4426,  4427,  4430,  4431,  4442,  4443,  4446,
    4447,  4458,  4459,  4460,  4461,  4462,  4463,  4474,  4475,  4477,  4478,
    4479,  4526,  4527,  4542,  4543,  4590,  4591,  4607,  4680,  4681,  4682,
    4683,  4685,  4687,  4698,  4699,  4700,  4701,  4702,  4703,  4713,  4715,
    4716,  4717,  4718,  4719,  4731,  4732,  4733,  4734,  4735,  4740,  4741,
    4743,  4748,  4749,  4750,  4751,  4758,  4759,  4764,  4765,  4766,  4767,
    4780,  4781,  4782,  4783,  4791,  4796,  4797,  4798,  4799,  4812,  4813,
    4814,  4815,  4829,  4830,  4831,  4845,  4847,  4863,  4940,  4941,  4942,
    4943,  4958,  4959,  4972,  4973,  4974,  4975,  4990,  4991,  5004,  5005,
    5006,  5007,  5020,  5021,  5022,  5023,  5036,  5037,  5038,  5039,  5052,
    5053,  5054,  5055,  5066,  5067,  5068,  5069,  5070,  5071,  5082,  5083,
    5084,  5085,  5086,  5087,  5097,  5099,  5100,  5101,  5102,  5103,  5113,
    5115,  5116,  5117,  5118,  5119,  5146,  5147,  5150,  5151,  5178,  5179,
    5180,  5181,  5182,  5183,  5210,  5211,  5214,  5215,  5242,  5243,  5245,
    5246,  5247,  5290,  5291,  5294,  5295,  5307,  5310,  5311,  5355,  5359,
    5375,  5406,  5407,  5420,  5421,  5422,  5423,  5438,  5439,  5450,  5451,
    5455,  5466,  5467,  5470,  5471,  5482,  5483,  5484,  5485,  5486,  5487,
    5498,  5499,  5500,  5501,  5502,  5503,  5541,  5542,  5543,  5546,  5547,
    5550,  5551,  5557,  5558,  5559,  5562,  5563,  5566,  5567,  5605,  5606,
    5607,  5610,  5611,  5614,  5615,  5621,  5622,  5623,  5626,  5627,  5630,
    5631,  5722,  5723,  5724,  5725,  5726,  5727,  5754,  5755,  5756,  5757,
    5758,  5759,  5767,  5775,  5783,  5790,  5791,  5799,  5803,  5804,  5805,
    5806,  5807,  5815,  5819,  5820,  5821,  5822,  5823,  5834,  5835,  5837,
    5838,  5839,  5847,  5850,  5851,  5853,  5854,  5855,  5867,  5868,  5869,
    5870,  5871,  5879,  5882,  5883,  5884,  5885,  5886,  5887,  5965,  5967,
    5982,  5983,  5997,  5999,  6014,  6015,  6023,  6030,  6031,  6039,  6046,
    6047,  6055,  6061,  6062,  6063,  6071,  6077,  6078,  6079,  6087,  6090,
    6091,  6094,  6095,  6103,  6106,  6107,  6110,  6111,  6119,  6122,  6123,
    6125,  6126,  6127,  6135,  6138,  6139,  6141,  6142,  6143,  6730,  6731,
    6735,  6746,  6747,  6750,  6751,  6763,  6766,  6767,  6779,  6782,  6783,
    6890,  6891,  6894,  6895,  6906,  6907,  6910,  6911,  6990,  6991,  7006,
    7007,  7022,  7023,  7038,  7039,  7147,  7150,  7151,  7163,  7166,  7167,
    7710,  7711,  7742,  7743,  7774,  7775,  7791,  7806,  7807,  7854,  7855,
    7870,  7871,  7918,  7919,  7934,  7935,  7967,  7983,  7999,  8015,  8031,
    8047,  8063,  8111,  8127,  8175,  8191,  13260, 13261, 13263, 13278, 13279,
    13311, 13726, 13727, 13740, 13741, 13742, 13743, 13758, 13759, 13770, 13771,
    13775, 13786, 13787, 13790, 13791, 13801, 13803, 13804, 13805, 13806, 13807,
    13817, 13818, 13819, 13820, 13821, 13822, 13823, 14025, 14027, 14031, 14043,
    14045, 14047, 14063, 14079, 14285, 14286, 14287, 14302, 14303, 14316, 14317,
    14318, 14319, 14334, 14335, 15420, 15421, 15423, 15485, 15486, 15487, 15615,
    15677, 15678, 15679, 15710, 15711, 15725, 15727, 15741, 15742, 15743, 15789,
    15791, 15805, 15807, 15838, 15839, 15853, 15855, 15869, 15870, 15871, 16191,
    16223, 16239, 16255, 16335, 16351, 16383, 23130, 23131, 23135, 23163, 23167,
    23295, 23390, 23391, 23422, 23423, 23531, 23535, 23547, 23550, 23551, 24415,
    24447, 24495, 24511, 24575, 31710, 31711, 31725, 31727, 31743, 32255, 32735,
    32767, 65535,
};

int main() {
  for (unsigned i = 0; i < (sizeof patterns / sizeof patterns[0]); i++) {
    int x1 = PADDING + (i % WIDTH_IN_BLOCKS) * PADDED_BLOCK_WIDTH;
    int y1 = PADDING + (i / WIDTH_IN_BLOCKS) * PADDED_BLOCK_HEIGHT;
    draw_pattern(x1, y1, BLOCK_WIDTH, BLOCK_HEIGHT, patterns[i]);
  }
  stbi_write_png("patterns.png", IMAGE_WIDTH, IMAGE_HEIGHT, 1, output,
                 IMAGE_WIDTH);
  return 0;
}

find-distinct-patterns.c

#include <stdio.h>

static unsigned int rotate(unsigned int p, int d) {
  // clockwise rotation
  // before:     after:
  // 0 1 2 3     c 8 4 0
  // 4 5 6 7     d 9 5 1
  // 8 9 a b     e a 6 2
  // c d e f     f b 7 3
  int i;
  for (i = 0; i < d * 2; i++) {
    p = (p | (p << 8)) & 0x00ff00ff;
    p = (p | (p << 4)) & 0x0f0f0f0f;
    p = (p | (p << 2)) & 0x33333333;
    p = (p | (p << 1)) & 0x55555555;
    p = ((p << 1) | (p >> 16)) & 0xFFFF;
  }
  return p;
}

static unsigned int flip(unsigned int p) {
  p = ((p >> 4) & 0x0F0F0F0F) | ((p & 0x0F0F0F0F) << 4);
  p = ((p >> 8) & 0x00FF00FF) | ((p & 0x00FF00FF) << 8);
  return p;
}

static unsigned int transpose_x(unsigned int p, int d) {
  int i;
  for (i = 0; i < d; i++)
    p = ((p & 0x7777) << 1) | ((p & 0x8888) >> 3);
  return p;
}

static unsigned int transpose_y(unsigned int p, int d) {
  int i;
  for (int i = 0; i < d; i++)
    p = ((p & 0x0FFF) << 4) | ((p & 0xF000) >> 12);
  return p;
}

static unsigned int transpose(unsigned int p, int x, int y) {
  return transpose_x(transpose_y(p, y), x);
}

#if 0
static unsigned int invert(unsigned int p) { return p ^ 0xFFFF; }

static void print_pattern(unsigned int p) {
  for (int y = 0; y < 4; y++) {
    for (int x = 0; x < 4; x++) {
      printf("%s", ((p >> ((y % 4) * 4 + (x % 4))) & 1) ? "[]" : "..");
    }
    putchar('\n');
  }
  printf("-\n");
}
#endif

#define NUM_PATTERNS 0x10000

unsigned char seen[NUM_PATTERNS];

int main() {
  int count = 0, x, y, r;
  unsigned i, p;
  for (i = 0; i < NUM_PATTERNS; i++) {
    if (seen[i])
      continue;
    count++;
    printf("%d, ", i);
    for (x = 0; x < 4; x++) {
      for (y = 0; y < 4; y++) {
        for (r = 0; r < 4; r++) {
          p = rotate(transpose_y(transpose_x(i, x), y), r);
          seen[p] = 1;
          seen[flip(p)] = 1;
#if 0
          seen[invert(p)] = 1;
          seen[invert(flip(p))] = 1;
#endif
        }
      }
    }
  }
  printf("\n");
  return 0;
}

Distinct 4x4 patterns: