about summary refs log tree commit diff
path: root/generator/pbmnoise.c
blob: e316dafcf6bef67d6bf89239b8f6e9c016757613 (plain) (blame)
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
/* pbmnoise.c - create a random bitmap of a specified size
                with a specified ratio of white/black pixels

   Written by Akira F Urushibata and contributed to the public domain 
   December 2021
*/

#include <math.h>
#include <string.h>
#include <assert.h>

#include "pm_c_util.h"
#include "shhopt.h"
#include "mallocvar.h"
#include "rand.h"
#include "nstring.h"

#include "pbm.h"



static void
parseFraction(const char *   const fraction,
              unsigned int * const numeratorP,
              unsigned int * const precisionP) {

    unsigned int numerator, denominator;

    sscanf(fraction, "%u/%u", &numerator, &denominator);

    if (denominator > 65536)
        pm_error("Denominator (%u) too large.", denominator);
    else if (denominator == 0 || (denominator & (denominator - 1)) != 0)
        pm_error("Denominator must be a power of two.  You specified %u.",
                 denominator);
    else if (numerator > denominator)
        pm_error("Invalid fraction (%s).  Denominator must be larger than "
                 "numerator.", fraction);
    else {
        /* Reduce fraction to lowest terms */
        unsigned int numerator2, denominator2;
            /* The fraction reduced to lowest terms */
        unsigned int precision2;

        if (numerator == 0) { /* all white image */
            numerator2   = 0;
            denominator2 = 1;
            precision2   = 0;
        } else if (numerator == denominator) { /* all black */
            numerator2   = 1;
            denominator2 = 1;
            precision2   = 0;
        } else {
            numerator2   = numerator;   /* initial value */
            denominator2 = denominator; /* initial value */

            while ((numerator2 & 0x01) != 0x01) {
                denominator2 /= 2;
                numerator2   /= 2;
            }
            precision2 = 1;
        }

      if (denominator != denominator2)
          pm_message("Ratio %u/%u = %u/%u",
                     numerator, denominator, numerator2, denominator2);

      *precisionP = (precision2 == 0) ? 0 : pm_maxvaltobits(denominator2 - 1);
          /* pm_maxvaltobits(N):  Max of N is 65535 */

      *numeratorP = numerator2;
    }
}



static void
setRatio(const char *   const ratioArg,
         unsigned int * const numeratorP,
         unsigned int * const precisionP) {
/*----------------------------------------------------------------------------
    Convert string "ratioArg" to ratio: numerator / (2 ^ precision) The input
    string must be in fraction "n/d" form and the denominator must be a power
    of 2.

    Ratio is the probability of one binary digit being "1".  The ratio of "1"
    (=PBM black) pixels in the entire output image will be close to this
    value.

    Most invalid strings are rejected here.
----------------------------------------------------------------------------*/
    if (strspn(ratioArg, "0123456789/") == strlen(ratioArg) &&
             ratioArg[0] != '/' &&
             ratioArg[strlen(ratioArg) - 1] != '/' &&
             strchr(ratioArg, '/') != NULL &&
             strchr(ratioArg, '/') == strrchr(ratioArg, '/'))
        parseFraction(ratioArg, numeratorP, precisionP);
    else
        pm_error("Invalid ratio: '%s'", ratioArg);
}



struct CmdlineInfo {
    /* All the information the user supplied in the command line,
       in a form easy for the program to use.
    */
    unsigned int width;
    unsigned int height;
    unsigned int numerator;
    unsigned int precision;
    unsigned int randomseed;
    unsigned int randomseedSpec;
    unsigned int bswap;   /* boolean */
    unsigned int pack;    /* boolean */
};



static void
parseCommandLine(int argc, const char ** argv,
                 struct CmdlineInfo * const cmdlineP) {
/*----------------------------------------------------------------------------
   Note that the file spec array we return is stored in the storage that
   was passed to us as the argv array.
-----------------------------------------------------------------------------*/
    optEntry *option_def;
        /* Instructions to pm_optParseOptions3 on how to parse our options.
         */
    optStruct3 opt;

    unsigned int option_def_index;
    const char * ratioArg;
    unsigned int ratioSpec;
    const char * endianArg;
    unsigned int endianSpec;

    MALLOCARRAY_NOFAIL(option_def, 100);

    option_def_index = 0;   /* incremented by OPTENTRY */
    OPTENT3(0, "ratio",         OPT_STRING, &ratioArg,
            &ratioSpec,                     0);
    OPTENT3(0, "randomseed",    OPT_UINT,   &cmdlineP->randomseed,
            &cmdlineP->randomseedSpec,      0);
    OPTENT3(0, "endian",        OPT_STRING, &endianArg,
            &endianSpec,                    0);
    OPTENT3(0, "pack",          OPT_FLAG,   NULL,
            &cmdlineP->pack,                0);

    opt.opt_table = option_def;
    opt.short_allowed = FALSE;  /* We have no short (old-fashioned) options */
    opt.allowNegNum = FALSE;  /* We may have parms that are negative numbers */

    pm_optParseOptions3(&argc, (char **)argv, opt, sizeof(opt), 0);
    /* Uses and sets argc, argv, and some of *cmdlineP and others. */
    free(option_def);

    if (ratioSpec)
        setRatio(ratioArg, &cmdlineP->numerator, &cmdlineP->precision);
    else {
        /* Set ratio to default: 1/2 */
        cmdlineP->numerator = 1;
        cmdlineP->precision = 1;
    }

    if (!endianSpec)
        cmdlineP->bswap = false;
    else {
        if      (streq(endianArg, "native"))
            cmdlineP->bswap = false;
        else if (streq(endianArg, "swap"))
            cmdlineP->bswap = true;
        else if (streq(endianArg, "big"))
            cmdlineP->bswap = (BYTE_ORDER == LITTLE_ENDIAN);
        else if (streq(endianArg, "little"))
            cmdlineP->bswap = (BYTE_ORDER != LITTLE_ENDIAN);
        else
            pm_error("Invalid value '%s' for -endian argument.", endianArg);
    }

    if (argc-1 != 2)
        pm_error("Wrong number of arguments (%d).  There are two "
                 "non-option arguments: width and height in pixels",
                 argc-1);
    else {
        cmdlineP->width  = pm_parse_width (argv[1]);
        cmdlineP->height = pm_parse_height(argv[2]);
    }
}



static void
writeSingleColorRaster(unsigned int const cols,
                       unsigned int const rows,
                       bit          const color,
                       FILE *       const ofP) {
/*-----------------------------------------------------------------------------
  Generate a single-color raster of color 'color', dimensions
  'cols' by 'rows', to output file *ofP.
-----------------------------------------------------------------------------*/
    unsigned int const lastColChar = (cols - 1) / 8;

    unsigned char * bitrow0;
    unsigned int i;

    bitrow0 = pbm_allocrow_packed(cols + 32);

    for (i = 0; i <= lastColChar; ++i)
        bitrow0[i] = color * 0xff;

    if (color != 0)
        pbm_cleanrowend_packed(bitrow0, cols);

    /* row end trimming, not necessary with white */

    {
        unsigned int row;
        for (row = 0; row < rows; ++row)
            pbm_writepbmrow_packed(ofP, bitrow0, cols, 0);
    }
    pbm_freerow(bitrow0);
}



static uint32_t
randombits(unsigned int       const precision,
           unsigned int       const numerator,
           struct pm_randSt * const randStP) {
/*----------------------------------------------------------------------------
  Generate 32 random bits so that for each bit the probability of "1"
  being generated is numerator / (2 ^ precision).

  How this works:

  Ratios such as 1/8, 7/8, 1/16, 15/16, 1/32, 31/32 are straightforward.  How
  do you get intermediate values such as 3/8, 5/8, 3/16, 5/16, 7/16?

  Imagine a set of 10 bits which are 90% 1, 10% 0 and a random number source
  which produces 1 and 0 in even proportions.

  Conduct "and" and "or" on these bits:

           0011111111 (90%)       0011111111 (90%)
      and) 0101010101 (50%)   or) 0101010101 (50%)
      ---------------------   --------------------
           0001010101 (45%)       0111111111 (95%)

  It can be seen from this example that an "and" operation gives a new ratio
  which is halfway between the old ratio (90% in this example) and 0%, while
  "or" gives one at the middle of the old ratio and 100% The corresponding
  binary operations for fixed-point fractions are: "right-shift by one and
  insert a 0 behind the fixed point" and "right-shift by one and insert a 1
  behind the fixed point" respecatbly.

  115/128 = 89.84% (near 90%)  In binary fix-point: 0.1110011
  0.01110011 = 115/256 = 44.92%
  0.11110011 = 243/256 = 94.92%

  So to achieve the desired ratio, start at the LSB (right end) of
  'numerator'.  Initialize the output bits to zero.  Conduct an "and" for each
  0 and an "or" for each 1 with a freshly drawn random number until the fixed
  point is reached.

  An "and" operation of a random number and zero always yields zero.  To avoid
  waste, we reduce terms to eliminate the trailing zeroes in 'numerator' and
  indicate the fixed point with 'precision'.  Each time the program is
  executed the location of the fixed point is set anew, but it stays constant
  until the program exits.
----------------------------------------------------------------------------*/
    unsigned int i;
    uint32_t mask;
    uint32_t retval;

    for (i = 0, mask = 0x01, retval=0x00000000;
         i < precision;
         ++i, mask <<= 1) {

        uint32_t const randval = pm_rand32(randStP);

        if ((numerator & mask) != 0 )
            retval |= randval;
        else
            retval &= randval;
    }
    return retval;
}



static uint32_t
swapWord(uint32_t const word) {
/*----------------------------------------------------------------------------
  Swap four bytes.
  This swap method works regardless of native system endianness.
----------------------------------------------------------------------------*/
    uint32_t const retval =
        ((word >> 24) & 0xff) |
        ((word >>  8) & 0xff00) |
        ((word <<  8) & 0xff0000) |
        ((word << 24) & 0xff000000)
        ;

    return retval;
}



static void
swapBitrow(unsigned char * const bitrow,
           unsigned int    const words,
           bool            const bswap) {
/*----------------------------------------------------------------------------
  Modify bits in 'bitrow', swapping as indicated.
----------------------------------------------------------------------------*/
    uint32_t * const bitrowByWord = (uint32_t *) bitrow;

    unsigned int wordCnt;

    for (wordCnt=0; wordCnt < words; ++wordCnt) {
        uint32_t const inWord = bitrowByWord[wordCnt];

        bitrowByWord[wordCnt] = bswap ? swapWord(inWord) : inWord;
    }
}



static void
pbmnoise(FILE *             const ofP,
         unsigned int       const cols,
         unsigned int       const rows,
         unsigned int       const numerator,
         unsigned int       const precision,
         bool               const bswap,
         struct pm_randSt * const randStP) {
/*----------------------------------------------------------------------------
  Default method of constructing rows.

  Generate pixels in units of 32 bits.

  If cols is not a multiple of 32, discard pixels beyond row end.
-----------------------------------------------------------------------------*/
    unsigned int const words = (cols + 31) / 32;

    unsigned char * bitrow;
    unsigned int row;
    unsigned int wordCnt;

    bitrow = pbm_allocrow_packed(cols + 32);

    for (row = 0; row < rows; ++row) {
        uint32_t * const bitrowByWord = (uint32_t *) bitrow;

        for (wordCnt = 0; wordCnt < words; ++wordCnt)
            bitrowByWord[wordCnt] = randombits(precision, numerator, randStP);

        if (bswap)
            swapBitrow(bitrow, words, bswap);

        pbm_cleanrowend_packed(bitrow, cols);
        pbm_writepbmrow_packed(ofP, bitrow, cols, 0);
    }
    pbm_freerow(bitrow);
}



static void
pbmnoise_packed(FILE *             const ofP,
                unsigned int       const cols,
                unsigned int       const rows,
                unsigned int       const numerator,
                unsigned int       const precision,
                bool               const bswap,
                struct pm_randSt * const randStP) {
/*----------------------------------------------------------------------------
  Alternate method of constructing rows.
  Like the default pbmnoise(), generate pixels in units of 32 bits
  but carry over unused pixel data at row end to the next row.
-----------------------------------------------------------------------------*/
    unsigned char * bitrow0;
    uint32_t * bitrowByWord;
    unsigned int offset;
    unsigned int row;
    uint32_t wordSave;    /* Pixels carried over to next row */

    bitrow0 = pbm_allocrow_packed(cols + 63);
    bitrowByWord = (uint32_t *) bitrow0;

    for (row = 0, offset = 0; row < rows; ++row) {
        if (offset == 0) {
            unsigned int const words = (cols + 31 ) / 32;

            unsigned int wordCnt;

            for (wordCnt = 0; wordCnt< words; ++wordCnt) {
                bitrowByWord[wordCnt] =
                    randombits(precision, numerator, randStP);
            }

            if (bswap)
                swapBitrow(bitrow0, words, bswap);

            wordSave = bitrowByWord[words - 1];

            pbm_cleanrowend_packed(bitrow0, cols);
            pbm_writepbmrow_packed(ofP, bitrow0, cols, 0);
            offset = cols % 32;
        } else {
            unsigned int const wordsToFetch = (cols - (32 - offset) + 31) / 32;
            unsigned int const lastWord = wordsToFetch;

            unsigned int wordCnt;

            bitrowByWord[0] = wordSave;

            for (wordCnt = 0; wordCnt < wordsToFetch; ++wordCnt) {
                bitrowByWord[wordCnt + 1] =
                    randombits(precision, numerator, randStP);
            }

            if (bswap)
                swapBitrow((unsigned char *) & bitrowByWord[1],
                           wordsToFetch, bswap);

            wordSave = bitrowByWord [lastWord];

            pbm_writepbmrow_bitoffset(ofP, bitrow0, cols, 0, offset);
            offset = (offset + cols) % 32;
        }
    }
    pbm_freerow(bitrow0);
}


int
main(int argc, const char *argv[]) {

    struct CmdlineInfo cmdline;

    pm_proginit(&argc, argv);

    parseCommandLine(argc, argv, &cmdline);

    pbm_writepbminit(stdout, cmdline.width, cmdline.height, 0);

    if (cmdline.precision == 0) {
        bit color;

        if (cmdline.numerator == 0)
            color = PBM_WHITE;
        else {
            assert (cmdline.numerator == 1);
            color = PBM_BLACK;
        }
        writeSingleColorRaster(cmdline.width, cmdline.height, color, stdout);
    } else if (cmdline.width % 32 == 0 || !cmdline.pack) {
        struct pm_randSt randSt;

        pm_randinit(&randSt);
        pm_srand2(&randSt, cmdline.randomseedSpec, cmdline.randomseed);

        pbmnoise(stdout, cmdline.width, cmdline.height,
                 cmdline.numerator, cmdline.precision,
                 cmdline.bswap, &randSt);

        pm_randterm(&randSt);
    } else {
        struct pm_randSt randSt;

        pm_randinit(&randSt);
        pm_srand2(&randSt, cmdline.randomseedSpec, cmdline.randomseed);

        pbmnoise_packed(stdout, cmdline.width, cmdline.height,
                        cmdline.numerator, cmdline.precision,
                        cmdline.bswap, &randSt);

        pm_randterm(&randSt);
    }
    return 0;
}