phoboslab/qoi.h

   1 /*
   2
   3 QOI - The “Quite OK Image” format for fast, lossless image compression
   4
   5 Dominic Szablewski - https://phoboslab.org
   6
   7
   8 -- LICENSE: The MIT License(MIT)
   9
  10 Copyright(c) 2021 Dominic Szablewski
  11
  12 Permission is hereby granted, free of charge, to any person obtaining a copy of
  13 this software and associated documentation files(the "Software"), to deal in
  14 the Software without restriction, including without limitation the rights to
  15 use, copy, modify, merge, publish, distribute, sublicense, and / or sell copies
  16 of the Software, and to permit persons to whom the Software is furnished to do
  17 so, subject to the following conditions :
  18 The above copyright notice and this permission notice shall be included in all
  19 copies or substantial portions of the Software.
  20 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  21 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  22 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
  23 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  24 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  25 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  26 SOFTWARE.
  27
  28
  29 -- About
  30
  31 QOI encodes and decodes images in a lossless format. An encoded QOI image is
  32 usually around 10--30% larger than a decently optimized PNG image.
  33
  34 QOI outperforms simpler PNG encoders in compression ratio and performance. QOI
  35 images are typically 20% smaller than PNGs written with stbi_image but 10%
  36 larger than with libpng. Encoding is 25-50x faster and decoding is 3-4x faster
  37 than stbi_image or libpng.
  38
  39
  40 -- Synopsis
  41
  42 // Define `QOI_IMPLEMENTATION` in *one* C/C++ file before including this
  43 // library to create the implementation.
  44
  45 #define QOI_IMPLEMENTATION
  46 #include "qoi.h"
  47
  48 // Load and decode a QOI image from the file system into a 32bbp RGBA buffer
  49 int width, height;
  50 void *rgba_pixels = qoi_read("image.qoi", &width, &height, 4);
  51
  52 // Encode and store an RGBA buffer to the file system
  53 qoi_write("image_new.qoi", rgba_pixels, width, height, 4);
  54
  55
  56 -- Documentation
  57
  58 This library provides the following functions;
  59 - qoi_read    -- read and decode a QOI file
  60 - qoi_decode  -- decode the raw bytes of a QOI image from memory
  61 - qoi_write   -- encode and write a QOI file
  62 - qoi_encode  -- encode an rgba buffer into a QOI image in memory
  63
  64 See the function declaration below for the signature and more information.
  65
  66 If you don't want/need the qoi_read and qoi_write functions, you can define
  67 QOI_NO_STDIO before including this library.
  68
  69 This library uses malloc() and free(). To supply your own malloc implementation
  70 you can define QOI_MALLOC and QOI_FREE before including this library.
  71
  72
  73 -- Data Format
  74
  75 A QOI file has a 12 byte header, followed by any number of data "chunks".
  76
  77 struct qoi_header_t {
  78         char [4];              // magic bytes "qoif"
  79         unsigned short width;  // image width in pixels (BE)
  80         unsigned short height; // image height in pixels (BE)
  81         unsigned int size;     // number of data bytes following this header (BE)
  82 };
  83
  84 The decoder and encoder start with {r: 0, g: 0, b: 0, a: 255} as the previous
  85 pixel value. Pixels are either encoded as
  86  - a run of the previous pixel
  87  - an index into a previously seen pixel
  88  - a difference to the previous pixel value in r,g,b,a
  89  - full r,g,b,a values
  90
  91 A running array[64] of previously seen pixel values is maintained by the encoder
  92 and decoder. Each pixel that is seen by the encoder and decoder is put into this
  93 array at the position (r^g^b^a) % 64. In the encoder, if the pixel value at this
  94 index matches the current pixel, this index position is written to the stream.
  95
  96 Each chunk starts with a 2, 3 or 4 bit tag, followed by a number of data bits.
  97 The bit length of chunks is divisible by 8 - i.e. all chunks are byte aligned.
  98
  99 QOI_INDEX {
 100         u8 tag  :  2;   // b00
 101         u8 idx  :  6;   // 6-bit index into the color index array: 0..63
 102 }
 103
 104 QOI_RUN_8 {
 105         u8 tag  :  3;   // b010
 106         u8 run  :  5;   // 5-bit run-length repeating the previous pixel: 1..32
 107 }
 108
 109 QOI_RUN_16 {
 110         u8 tag  :  3;   // b011
 111         u16 run : 13;   // 13-bit run-length repeating the previous pixel: 33..8224
 112 }
 113
 114 QOI_DIFF_8 {
 115         u8 tag  :  2;   // b10
 116         u8 dr   :  2;   // 2-bit   red channel difference: -1..2
 117         u8 dg   :  2;   // 2-bit green channel difference: -1..2
 118         u8 db   :  2;   // 2-bit  blue channel difference: -1..2
 119 }
 120
 121 QOI_DIFF_16 {
 122         u8 tag  :  3;   // b110
 123         u8 dr   :  5;   // 5-bit   red channel difference: -15..16
 124         u8 dg   :  4;   // 4-bit green channel difference:  -7.. 8
 125         u8 db   :  4;   // 4-bit  blue channel difference:  -7.. 8
 126 }
 127
 128 QOI_DIFF_24 {
 129         u8 tag  :  4;   // b1110
 130         u8 dr   :  5;   // 5-bit   red channel difference: -15..16
 131         u8 dg   :  5;   // 5-bit green channel difference: -15..16
 132         u8 db   :  5;   // 5-bit  blue channel difference: -15..16
 133         u8 da   :  5;   // 5-bit alpha channel difference: -15..16
 134 }
 135
 136 QOI_COLOR {
 137         u8 tag  :  4;   // b1111
 138         u8 has_r:  1;   //   red byte follows
 139         u8 has_g:  1;   // green byte follows
 140         u8 has_b:  1;   //  blue byte follows
 141         u8 has_a:  1;   // alpha byte follows
 142         u8 r;           //   red value if has_r == 1: 0..255
 143         u8 g;           // green value if has_g == 1: 0..255
 144         u8 b;           //  blue value if has_b == 1: 0..255
 145         u8 a;           // alpha value if has_a == 1: 0..255
 146 }
 147
 148 The byte stream is padded with 4 zero bytes. Size the longest chunk we can
 149 encounter is 5 bytes (QOI_COLOR with RGBA set), with this padding we just have
 150 to check for an overrun once per decode loop iteration.
 151
 152 */
 153
 154
 155 // -----------------------------------------------------------------------------
 156 // Header - Public functions
 157
 158 #ifndef QOI_H
 159 #define QOI_H
 160
 161 #ifdef __cplusplus
 162 extern "C" {
 163 #endif
 164
 165 #ifndef QOI_NO_STDIO
 166
 167 // Encode raw RGB or RGBA pixels into a QOI image write it to the file system.
 168 // w and h denote the the width and height of the pixel data. channels must be
 169 // either 3 for RGB data or 4 for RGBA.
 170 // The function returns 0 on failure (invalid parameters, or fopen or malloc
 171 // failed) or the number of bytes written on success.
 172
 173 int qoi_write(const char *filename, const void *data, int w, int h, int channels);
 174
 175
 176 // Read and decode a QOI image from the file system into either raw RGB
 177 // (channels=3) or RGBA (channels=4) pixel data.
 178 // The function either returns NULL on failure (invalid data, or malloc or fopen
 179 // failed) or a pointer to the decoded pixels. On success out_w and out_h will
 180 // be set to the width and height of the decoded image.
 181 // The returned pixel data should be free()d after use.
 182
 183 void *qoi_read(const char *filename, int *out_w, int *out_h, int channels);
 184
 185 #endif // QOI_NO_STDIO
 186
 187
 188 // Encode raw RGB or RGBA pixels into a QOI image in memory. w and h denote the
 189 // width and height of the pixel data. channels must be either 3 for RGB data
 190 // or 4 for RGBA.
 191 // The function either returns NULL on failure (invalid parameters or malloc
 192 // failed) or a pointer to the encoded data on success. On success the out_len
 193 // is set to the size in bytes of the encoded data.
 194 // The returned qoi data should be free()d after user.
 195
 196 void *qoi_encode(const void *data, int w, int h, int channels, int *out_len);
 197
 198
 199 // Decode a QOI image from memory into either raw RGB (channels=3) or RGBA
 200 // (channels=4) pixel data.
 201 // The function either returns NULL on failure (invalid parameters or malloc
 202 // failed) or a pointer to the decoded pixels. On success out_w and out_h will
 203 // be set to the width and height of the decoded image.
 204 // The returned pixel data should be free()d after use.
 205
 206 void *qoi_decode(const void *data, int size, int *out_w, int *out_h, int channels);
 207
 208 #ifdef __cplusplus
 209 }
 210 #endif
 211 #endif // QOI_H
 212
 213
 214 // -----------------------------------------------------------------------------
 215 // Implementation
 216
 217 #ifdef QOI_IMPLEMENTATION
 218 #include <stdlib.h>
 219
 220 #ifndef QOI_MALLOC
 221         #define QOI_MALLOC(sz) malloc(sz)
 222         #define QOI_FREE(p)    free(p)
 223 #endif
 224
 225 #define QOI_INDEX   0x00 // 00xxxxxx
 226 #define QOI_RUN_8   0x40 // 010xxxxx
 227 #define QOI_RUN_16  0x60 // 011xxxxx
 228 #define QOI_DIFF_8  0x80 // 10xxxxxx
 229 #define QOI_DIFF_16 0xc0 // 110xxxxx
 230 #define QOI_DIFF_24 0xe0 // 1110xxxx
 231 #define QOI_COLOR   0xf0 // 1111xxxx
 232
 233 #define QOI_MASK_2  0xc0 // 11000000
 234 #define QOI_MASK_3  0xe0 // 11100000
 235 #define QOI_MASK_4  0xf0 // 11110000
 236
 237 #define QOI_COLOR_HASH(C) (C.rgba.r ^ C.rgba.g ^ C.rgba.b ^ C.rgba.a)
 238 #define QOI_MAGIC \
 239         (((unsigned int)'q') << 24 | ((unsigned int)'o') << 16 | \
 240          ((unsigned int)'i') <<  8 | ((unsigned int)'f'))
 241 #define QOI_HEADER_SIZE 12
 242 #define QOI_PADDING 4
 243
 244 typedef union {
 245         struct { unsigned char r, g, b, a; } rgba;
 246         unsigned int v;
 247 } qoi_rgba_t;
 248
 249 void qoi_write_16(unsigned char *bytes, int *p, unsigned short v) {
 250         bytes[(*p)++] = (0xff00 & v) >> 8;
 251         bytes[(*p)++] = (0xff & v);
 252 }
 253
 254 void qoi_write_32(unsigned char *bytes, int *p, unsigned int v) {
 255         qoi_write_16(bytes, p, (v & 0xffff0000) >> 16);
 256         qoi_write_16(bytes, p, (v & 0xffff));
 257 }
 258
 259 unsigned int qoi_read_16(const unsigned char *bytes, int *p) {
 260         unsigned int a = bytes[(*p)++];
 261         unsigned int b = bytes[(*p)++];
 262         return (a << 8) | b;
 263 }
 264
 265 unsigned int qoi_read_32(const unsigned char *bytes, int *p) {
 266         unsigned int a = qoi_read_16(bytes, p);
 267         unsigned int b = qoi_read_16(bytes, p);
 268         return (a << 16) | b;
 269 }
 270
 271 void *qoi_encode(const void *data, int w, int h, int channels, int *out_len) {
 272         if (
 273                 data == NULL || out_len == NULL ||
 274                 w <= 0 || w >= (1 << 16) ||
 275                 h <= 0 || h >= (1 << 16) ||
 276                 channels < 3 || channels > 4
 277         ) {
 278                 return NULL;
 279         }
 280
 281         int max_size = w * h * (channels + 1) + QOI_HEADER_SIZE + QOI_PADDING;
 282         int p = 0;
 283         unsigned char *bytes = QOI_MALLOC(max_size);
 284         if (!bytes) {
 285                 return NULL;
 286         }
 287
 288         qoi_write_32(bytes, &p, QOI_MAGIC);
 289         qoi_write_16(bytes, &p, w);
 290         qoi_write_16(bytes, &p, h);
 291         qoi_write_32(bytes, &p, 0); // size, will be set later
 292
 293         const unsigned char *pixels = (const unsigned char *)data;
 294
 295         qoi_rgba_t index[64] = {0};
 296
 297         int run = 0;
 298         qoi_rgba_t px_prev = {.rgba = {.r = 0, .g = 0, .b = 0, .a = 255}};
 299         qoi_rgba_t px = px_prev;
 300
 301         int px_len = w * h * channels;
 302         int px_end = px_len - channels;
 303         for (int px_pos = 0; px_pos < px_len; px_pos += channels) {
 304                 if (channels == 4) {
 305                         px = *(qoi_rgba_t *)(pixels + px_pos);
 306                 }
 307                 else {
 308                         px.rgba.r = pixels[px_pos];
 309                         px.rgba.g = pixels[px_pos+1];
 310                         px.rgba.b = pixels[px_pos+2];
 311                 }
 312
 313                 if (px.v == px_prev.v) {
 314                         run++;
 315                 }
 316
 317                 if (run > 0 && (run == 0x2020 || px.v != px_prev.v || px_pos == px_end)) {
 318                         if (run < 33) {
 319                                 run -= 1;
 320                                 bytes[p++] = QOI_RUN_8 | run;
 321                         }
 322                         else {
 323                                 run -= 33;
 324                                 bytes[p++] = QOI_RUN_16 | run >> 8;
 325                                 bytes[p++] = run;
 326                         }
 327                         run = 0;
 328                 }
 329
 330                 if (px.v != px_prev.v) {
 331                         int index_pos = QOI_COLOR_HASH(px) % 64;
 332
 333                         if (index[index_pos].v == px.v) {
 334                                 bytes[p++] = QOI_INDEX | index_pos;
 335                         }
 336                         else {
 337                                 index[index_pos] = px;
 338
 339                                 int vr = px.rgba.r - px_prev.rgba.r;
 340                                 int vg = px.rgba.g - px_prev.rgba.g;
 341                                 int vb = px.rgba.b - px_prev.rgba.b;
 342                                 int va = px.rgba.a - px_prev.rgba.a;
 343
 344                                 if (
 345                                         vr > -16 && vr < 17 && vg > -16 && vg < 17 &&
 346                                         vb > -16 && vb < 17 && va > -16 && va < 17
 347                                 ) {
 348                                         if (
 349                                                 va == 0 && vr > -2 && vr < 3 &&
 350                                                 vg > -2 && vg < 3 && vb > -2 && vb < 3
 351                                         ) {
 352                                                 bytes[p++] = QOI_DIFF_8 | ((vr + 1) << 4) | (vg + 1) << 2 | (vb + 1);
 353                                         }
 354                                         else if (
 355                                                 va == 0 && vr > -16 && vr < 17 &&
 356                                                 vg > -8 && vg < 9 && vb > -8 && vb < 9
 357                                         ) {
 358                                                 bytes[p++] = QOI_DIFF_16 | (vr + 15);
 359                                                 bytes[p++] = ((vg + 7) << 4) | (vb + 7);
 360                                         }
 361                                         else {
 362                                                 bytes[p++] = QOI_DIFF_24 | ((vr + 15) >> 1);
 363                                                 bytes[p++] = ((vr + 15) << 7) | ((vg + 15) << 2) | ((vb + 15) >> 3);
 364                                                 bytes[p++] = ((vb + 15) << 5) | (va + 15);
 365                                         }
 366                                 }
 367                                 else {
 368                                         bytes[p++] = QOI_COLOR | (vr?8:0)|(vg?4:0)|(vb?2:0)|(va?1:0);
 369                                         if (vr) { bytes[p++] = px.rgba.r; }
 370                                         if (vg) { bytes[p++] = px.rgba.g; }
 371                                         if (vb) { bytes[p++] = px.rgba.b; }
 372                                         if (va) { bytes[p++] = px.rgba.a; }
 373                                 }
 374                         }
 375                 }
 376                 px_prev = px;
 377         }
 378
 379         for (int i = 0; i < QOI_PADDING; i++) {
 380                 bytes[p++] = 0;
 381         }
 382
 383         int data_len = p - QOI_HEADER_SIZE;
 384         *out_len = p;
 385
 386         p = 8;
 387         qoi_write_32(bytes, &p, data_len);
 388         return bytes;
 389 }
 390
 391 void *qoi_decode(const void *data, int size, int *out_w, int *out_h, int channels) {
 392         if (channels < 3 || channels > 4 || size < QOI_HEADER_SIZE) {
 393                 return NULL;
 394         }
 395
 396         const unsigned char *bytes = (const unsigned char *)data;
 397         int p = 0;
 398
 399         int magic = qoi_read_32(bytes, &p);
 400         int w = qoi_read_16(bytes, &p);
 401         int h = qoi_read_16(bytes, &p);
 402         int data_len = qoi_read_32(bytes, &p);
 403
 404         if (
 405                 w == 0 || h == 0 || magic != QOI_MAGIC ||
 406                 size != data_len + QOI_HEADER_SIZE
 407         ) {
 408                 return NULL;
 409         }
 410
 411         int px_len = w * h * channels;
 412         unsigned char *pixels = QOI_MALLOC(px_len);
 413         if (!pixels) {
 414                 return NULL;
 415         }
 416
 417         qoi_rgba_t px = {.rgba = {.r = 0, .g = 0, .b = 0, .a = 255}};
 418         qoi_rgba_t index[64] = {0};
 419
 420         int run = 0;
 421         int chunks_len = size - QOI_PADDING;
 422         for (int px_pos = 0; px_pos < px_len; px_pos += channels) {
 423                 if (run > 0) {
 424                         run--;
 425                 }
 426                 else if (p < chunks_len) {
 427                         int b1 = bytes[p++];
 428
 429                         if ((b1 & QOI_MASK_2) == QOI_INDEX) {
 430                                 px = index[b1 ^ QOI_INDEX];
 431                         }
 432                         else if ((b1 & QOI_MASK_3) == QOI_RUN_8) {
 433                                 run = (b1 & 0x1f);
 434                         }
 435                         else if ((b1 & QOI_MASK_3) == QOI_RUN_16) {
 436                                 int b2 = bytes[p++];
 437                                 run = (((b1 & 0x1f) << 8) | (b2)) + 32;
 438                         }
 439                         else if ((b1 & QOI_MASK_2) == QOI_DIFF_8) {
 440                                 px.rgba.r += ((b1 >> 4) & 0x03) - 1;
 441                                 px.rgba.g += ((b1 >> 2) & 0x03) - 1;
 442                                 px.rgba.b += ( b1       & 0x03) - 1;
 443                         }
 444                         else if ((b1 & QOI_MASK_3) == QOI_DIFF_16) {
 445                                 int b2 = bytes[p++];
 446                                 px.rgba.r += (b1 & 0x1f) - 15;
 447                                 px.rgba.g += (b2 >> 4) - 7;
 448                                 px.rgba.b += (b2 & 0x0f) - 7;
 449                         }
 450                         else if ((b1 & QOI_MASK_4) == QOI_DIFF_24) {
 451                                 int b2 = bytes[p++];
 452                                 int b3 = bytes[p++];
 453                                 px.rgba.r += (((b1 & 0x0f) << 1) | (b2 >> 7)) - 15;
 454                                 px.rgba.g +=  ((b2 & 0x7c) >> 2) - 15;
 455                                 px.rgba.b += (((b2 & 0x03) << 3) | ((b3 & 0xe0) >> 5)) - 15;
 456                                 px.rgba.a +=   (b3 & 0x1f) - 15;
 457                         }
 458                         else if ((b1 & QOI_MASK_4) == QOI_COLOR) {
 459                                 if (b1 & 8) { px.rgba.r = bytes[p++]; }
 460                                 if (b1 & 4) { px.rgba.g = bytes[p++]; }
 461                                 if (b1 & 2) { px.rgba.b = bytes[p++]; }
 462                                 if (b1 & 1) { px.rgba.a = bytes[p++]; }
 463                         }
 464
 465                         index[QOI_COLOR_HASH(px) % 64] = px;
 466                 }
 467
 468                 if (channels == 4) {
 469                         *(qoi_rgba_t*)(pixels + px_pos) = px;
 470                 }
 471                 else {
 472                         pixels[px_pos] = px.rgba.r;
 473                         pixels[px_pos+1] = px.rgba.g;
 474                         pixels[px_pos+2] = px.rgba.b;
 475                 }
 476         }
 477
 478         *out_w = w;
 479         *out_h = h;
 480         return pixels;
 481 }
 482
 483 #ifndef QOI_NO_STDIO
 484 #include <stdio.h>
 485
 486 int qoi_write(const char *filename, const void *data, int w, int h, int channels) {
 487         int size;
 488         void *encoded = qoi_encode(data, w, h, channels, &size);
 489         if (!encoded) {
 490                 return 0;
 491         }
 492
 493         FILE *f = fopen(filename, "wb");
 494         if (!f) {
 495                 QOI_FREE(encoded);
 496                 return 0;
 497         }
 498
 499         fwrite(encoded, 1, size, f);
 500         fclose(f);
 501         QOI_FREE(encoded);
 502         return size;
 503 }
 504
 505 void *qoi_read(const char *filename, int *out_w, int *out_h, int channels) {
 506         FILE *f = fopen(filename, "rb");
 507         if (!f) {
 508                 return NULL;
 509         }
 510
 511         fseek(f, 0, SEEK_END);
 512         int size = ftell(f);
 513         fseek(f, 0, SEEK_SET);
 514
 515         void *data = QOI_MALLOC(size);
 516         if (!data) {
 517                 return NULL;
 518         }
 519
 520         int bytes_read = fread(data, 1, size, f);
 521         fclose(f);
 522
 523         void *pixels = qoi_decode(data, bytes_read, out_w, out_h, channels);
 524         QOI_FREE(data);
 525         return pixels;
 526 }
 527
 528 #endif // QOI_NO_STDIO
 529 #endif // QOI_IMPLEMENTATION