1/* 
2 
3Copyright (c) 2021, Dominic Szablewski - https://phoboslab.org 
4SPDX-License-Identifier: MIT 
5 
6 
7QOI - The "Quite OK Image" format for fast, lossless image compression 
8 
9-- About 
10 
11QOI encodes and decodes images in a lossless format. Compared to stb_image and 
12stb_image_write QOI offers 20x-50x faster encoding, 3x-4x faster decoding and 
1320% better compression. 
14 
15 
16-- Synopsis 
17 
18// Define `QOI_IMPLEMENTATION` in *one* C/C++ file before including this 
19// library to create the implementation. 
20 
21#define QOI_IMPLEMENTATION 
22#include "qoi.h" 
23 
24// Encode and store an RGBA buffer to the file system. The qoi_desc describes 
25// the input pixel data. 
26qoi_write("image_new.qoi", rgba_pixels, &(qoi_desc){ 
27 .width = 1920, 
28 .height = 1080, 
29 .channels = 4, 
30 .colorspace = QOI_SRGB 
31}); 
32 
33// Load and decode a QOI image from the file system into a 32bbp RGBA buffer. 
34// The qoi_desc struct will be filled with the width, height, number of channels 
35// and colorspace read from the file header. 
36qoi_desc desc; 
37void *rgba_pixels = qoi_read("image.qoi", &desc, 4); 
38 
39 
40 
41-- Documentation 
42 
43This library provides the following functions; 
44- qoi_read -- read and decode a QOI file 
45- qoi_decode -- decode the raw bytes of a QOI image from memory 
46- qoi_write -- encode and write a QOI file 
47- qoi_encode -- encode an rgba buffer into a QOI image in memory 
48 
49See the function declaration below for the signature and more information. 
50 
51If you don't want/need the qoi_read and qoi_write functions, you can define 
52QOI_NO_STDIO before including this library. 
53 
54This library uses malloc() and free(). To supply your own malloc implementation 
55you can define QOI_MALLOC and QOI_FREE before including this library. 
56 
57This library uses memset() to zero-initialize the index. To supply your own 
58implementation you can define QOI_ZEROARR before including this library. 
59 
60 
61-- Data Format 
62 
63A QOI file has a 14 byte header, followed by any number of data "chunks" and an 
648-byte end marker. 
65 
66struct qoi_header_t { 
67 char magic[4]; // magic bytes "qoif" 
68 uint32_t width; // image width in pixels (BE) 
69 uint32_t height; // image height in pixels (BE) 
70 uint8_t channels; // 3 = RGB, 4 = RGBA 
71 uint8_t colorspace; // 0 = sRGB with linear alpha, 1 = all channels linear 
72}; 
73 
74Images are encoded row by row, left to right, top to bottom. The decoder and 
75encoder start with {r: 0, g: 0, b: 0, a: 255} as the previous pixel value. An 
76image is complete when all pixels specified by width * height have been covered. 
77 
78Pixels are encoded as 
79 - a run of the previous pixel 
80 - an index into an array of previously seen pixels 
81 - a difference to the previous pixel value in r,g,b 
82 - full r,g,b or r,g,b,a values 
83 
84The color channels are assumed to not be premultiplied with the alpha channel 
85("un-premultiplied alpha"). 
86 
87A running array[64] (zero-initialized) of previously seen pixel values is 
88maintained by the encoder and decoder. Each pixel that is seen by the encoder 
89and decoder is put into this array at the position formed by a hash function of 
90the color value. In the encoder, if the pixel value at the index matches the 
91current pixel, this index position is written to the stream as QOI_OP_INDEX. 
92The hash function for the index is: 
93 
94 index_position = (r * 3 + g * 5 + b * 7 + a * 11) % 64 
95 
96Each chunk starts with a 2- or 8-bit tag, followed by a number of data bits. The 
97bit length of chunks is divisible by 8 - i.e. all chunks are byte aligned. All 
98values encoded in these data bits have the most significant bit on the left. 
99 
100The 8-bit tags have precedence over the 2-bit tags. A decoder must check for the 
101presence of an 8-bit tag first. 
102 
103The byte stream's end is marked with 7 0x00 bytes followed a single 0x01 byte. 
104 
105 
106The possible chunks are: 
107 
108 
109.- QOI_OP_INDEX ----------. 
110| Byte[0] | 
111| 7 6 5 4 3 2 1 0 | 
112|-------+-----------------| 
113| 0 0 | index | 
114`-------------------------` 
1152-bit tag b00 
1166-bit index into the color index array: 0..63 
117 
118A valid encoder must not issue 2 or more consecutive QOI_OP_INDEX chunks to the 
119same index. QOI_OP_RUN should be used instead. 
120 
121 
122.- QOI_OP_DIFF -----------. 
123| Byte[0] | 
124| 7 6 5 4 3 2 1 0 | 
125|-------+-----+-----+-----| 
126| 0 1 | dr | dg | db | 
127`-------------------------` 
1282-bit tag b01 
1292-bit red channel difference from the previous pixel between -2..1 
1302-bit green channel difference from the previous pixel between -2..1 
1312-bit blue channel difference from the previous pixel between -2..1 
132 
133The difference to the current channel values are using a wraparound operation, 
134so "1 - 2" will result in 255, while "255 + 1" will result in 0. 
135 
136Values are stored as unsigned integers with a bias of 2. E.g. -2 is stored as 
1370 (b00). 1 is stored as 3 (b11). 
138 
139The alpha value remains unchanged from the previous pixel. 
140 
141 
142.- QOI_OP_LUMA -------------------------------------. 
143| Byte[0] | Byte[1] | 
144| 7 6 5 4 3 2 1 0 | 7 6 5 4 3 2 1 0 | 
145|-------+-----------------+-------------+-----------| 
146| 1 0 | green diff | dr - dg | db - dg | 
147`---------------------------------------------------` 
1482-bit tag b10 
1496-bit green channel difference from the previous pixel -32..31 
1504-bit red channel difference minus green channel difference -8..7 
1514-bit blue channel difference minus green channel difference -8..7 
152 
153The green channel is used to indicate the general direction of change and is 
154encoded in 6 bits. The red and blue channels (dr and db) base their diffs off 
155of the green channel difference and are encoded in 4 bits. I.e.: 
156 dr_dg = (cur_px.r - prev_px.r) - (cur_px.g - prev_px.g) 
157 db_dg = (cur_px.b - prev_px.b) - (cur_px.g - prev_px.g) 
158 
159The difference to the current channel values are using a wraparound operation, 
160so "10 - 13" will result in 253, while "250 + 7" will result in 1. 
161 
162Values are stored as unsigned integers with a bias of 32 for the green channel 
163and a bias of 8 for the red and blue channel. 
164 
165The alpha value remains unchanged from the previous pixel. 
166 
167 
168.- QOI_OP_RUN ------------. 
169| Byte[0] | 
170| 7 6 5 4 3 2 1 0 | 
171|-------+-----------------| 
172| 1 1 | run | 
173`-------------------------` 
1742-bit tag b11 
1756-bit run-length repeating the previous pixel: 1..62 
176 
177The run-length is stored with a bias of -1. Note that the run-lengths 63 and 64 
178(b111110 and b111111) are illegal as they are occupied by the QOI_OP_RGB and 
179QOI_OP_RGBA tags. 
180 
181 
182.- QOI_OP_RGB ------------------------------------------. 
183| Byte[0] | Byte[1] | Byte[2] | Byte[3] | 
184| 7 6 5 4 3 2 1 0 | 7 .. 0 | 7 .. 0 | 7 .. 0 | 
185|-------------------------+---------+---------+---------| 
186| 1 1 1 1 1 1 1 0 | red | green | blue | 
187`-------------------------------------------------------` 
1888-bit tag b11111110 
1898-bit red channel value 
1908-bit green channel value 
1918-bit blue channel value 
192 
193The alpha value remains unchanged from the previous pixel. 
194 
195 
196.- QOI_OP_RGBA ---------------------------------------------------. 
197| Byte[0] | Byte[1] | Byte[2] | Byte[3] | Byte[4] | 
198| 7 6 5 4 3 2 1 0 | 7 .. 0 | 7 .. 0 | 7 .. 0 | 7 .. 0 | 
199|-------------------------+---------+---------+---------+---------| 
200| 1 1 1 1 1 1 1 1 | red | green | blue | alpha | 
201`-----------------------------------------------------------------` 
2028-bit tag b11111111 
2038-bit red channel value 
2048-bit green channel value 
2058-bit blue channel value 
2068-bit alpha channel value 
207 
208*/ 
209 
210 
211/* ----------------------------------------------------------------------------- 
212Header - Public functions */ 
213 
214#ifndef QOI_H 
215#define QOI_H 
216 
217#ifdef __cplusplus 
218extern "C" { 
219#endif 
220 
221/* A pointer to a qoi_desc struct has to be supplied to all of qoi's functions. 
222It describes either the input format (for qoi_write and qoi_encode), or is 
223filled with the description read from the file header (for qoi_read and 
224qoi_decode). 
225 
226The colorspace in this qoi_desc is an enum where 
227 0 = sRGB, i.e. gamma scaled RGB channels and a linear alpha channel 
228 1 = all channels are linear 
229You may use the constants QOI_SRGB or QOI_LINEAR. The colorspace is purely 
230informative. It will be saved to the file header, but does not affect 
231how chunks are en-/decoded. */ 
232 
233#define QOI_SRGB 0 
234#define QOI_LINEAR 1 
235 
236typedef struct { 
237 unsigned int width; 
238 unsigned int height; 
239 unsigned char channels; 
240 unsigned char colorspace; 
241} qoi_desc; 
242 
243#ifndef QOI_NO_STDIO 
244 
245/* Encode raw RGB or RGBA pixels into a QOI image and write it to the file 
246system. The qoi_desc struct must be filled with the image width, height, 
247number of channels (3 = RGB, 4 = RGBA) and the colorspace. 
248 
249The function returns 0 on failure (invalid parameters, or fopen or malloc 
250failed) or the number of bytes written on success. */ 
251 
252int qoi_write(const char *filename, const void *data, const qoi_desc *desc); 
253 
254 
255/* Read and decode a QOI image from the file system. If channels is 0, the 
256number of channels from the file header is used. If channels is 3 or 4 the 
257output format will be forced into this number of channels. 
258 
259The function either returns NULL on failure (invalid data, or malloc or fopen 
260failed) or a pointer to the decoded pixels. On success, the qoi_desc struct 
261will be filled with the description from the file header. 
262 
263The returned pixel data should be free()d after use. */ 
264 
265void *qoi_read(const char *filename, qoi_desc *desc, int channels); 
266 
267#endif /* QOI_NO_STDIO */ 
268 
269 
270/* Encode raw RGB or RGBA pixels into a QOI image in memory. 
271 
272The function either returns NULL on failure (invalid parameters or malloc 
273failed) or a pointer to the encoded data on success. On success the out_len 
274is set to the size in bytes of the encoded data. 
275 
276The returned qoi data should be free()d after use. */ 
277 
278void *qoi_encode(const void *data, const qoi_desc *desc, int *out_len); 
279 
280 
281/* Decode a QOI image from memory. 
282 
283The function either returns NULL on failure (invalid parameters or malloc 
284failed) or a pointer to the decoded pixels. On success, the qoi_desc struct 
285is filled with the description from the file header. 
286 
287The returned pixel data should be free()d after use. */ 
288 
289void *qoi_decode(const void *data, int size, qoi_desc *desc, int channels); 
290 
291 
292#ifdef __cplusplus 
293} 
294#endif 
295#endif /* QOI_H */ 
296 
297 
298/* ----------------------------------------------------------------------------- 
299Implementation */ 
300 
301#ifdef QOI_IMPLEMENTATION 
302#include <stdlib.h> 
303#include <string.h> 
304 
305#ifndef QOI_MALLOC 
306 #define QOI_MALLOC(sz) malloc(sz) 
307 #define QOI_FREE(p) free(p) 
308#endif 
309#ifndef QOI_ZEROARR 
310 #define QOI_ZEROARR(a) memset((a),0,sizeof(a)) 
311#endif 
312 
313#define QOI_OP_INDEX 0x00 /* 00xxxxxx */ 
314#define QOI_OP_DIFF 0x40 /* 01xxxxxx */ 
315#define QOI_OP_LUMA 0x80 /* 10xxxxxx */ 
316#define QOI_OP_RUN 0xc0 /* 11xxxxxx */ 
317#define QOI_OP_RGB 0xfe /* 11111110 */ 
318#define QOI_OP_RGBA 0xff /* 11111111 */ 
319 
320#define QOI_MASK_2 0xc0 /* 11000000 */ 
321 
322#define QOI_COLOR_HASH(C) (C.rgba.r*3 + C.rgba.g*5 + C.rgba.b*7 + C.rgba.a*11) 
323#define QOI_MAGIC \ 
324 (((unsigned int)'q') << 24 | ((unsigned int)'o') << 16 | \ 
325 ((unsigned int)'i') << 8 | ((unsigned int)'f')) 
326#define QOI_HEADER_SIZE 14 
327 
328/* 2GB is the max file size that this implementation can safely handle. We guard 
329against anything larger than that, assuming the worst case with 5 bytes per 
330pixel, rounded down to a nice clean value. 400 million pixels ought to be 
331enough for anybody. */ 
332#define QOI_PIXELS_MAX ((unsigned int)400000000) 
333 
334typedef union { 
335 struct { unsigned char r, g, b, a; } rgba; 
336 unsigned int v; 
337} qoi_rgba_t; 
338 
339static const unsigned char qoi_padding[8] = {0,0,0,0,0,0,0,1}; 
340 
341static void qoi_write_32(unsigned char *bytes, int *p, unsigned int v) { 
342 bytes[(*p)++] = (0xff000000 & v) >> 24; 
343 bytes[(*p)++] = (0x00ff0000 & v) >> 16; 
344 bytes[(*p)++] = (0x0000ff00 & v) >> 8; 
345 bytes[(*p)++] = (0x000000ff & v); 
346} 
347 
348static unsigned int qoi_read_32(const unsigned char *bytes, int *p) { 
349 unsigned int a = bytes[(*p)++]; 
350 unsigned int b = bytes[(*p)++]; 
351 unsigned int c = bytes[(*p)++]; 
352 unsigned int d = bytes[(*p)++]; 
353 return a << 24 | b << 16 | c << 8 | d; 
354} 
355 
356void *qoi_encode(const void *data, const qoi_desc *desc, int *out_len) { 
357 int i, max_size, p, run; 
358 int px_len, px_end, px_pos, channels; 
359 unsigned char *bytes; 
360 const unsigned char *pixels; 
361 qoi_rgba_t index[64]; 
362 qoi_rgba_t px, px_prev; 
363 
364 if ( 
365 data == NULL || out_len == NULL || desc == NULL || 
366 desc->width == 0 || desc->height == 0 || 
367 desc->channels < 3 || desc->channels > 4 || 
368 desc->colorspace > 1 || 
369 desc->height >= QOI_PIXELS_MAX / desc->width 
370 ) { 
371 return NULL; 
372 } 
373 
374 max_size = 
375 desc->width * desc->height * (desc->channels + 1) + 
376 QOI_HEADER_SIZE + sizeof(qoi_padding); 
377 
378 p = 0; 
379 bytes = (unsigned char *) QOI_MALLOC(max_size); 
380 if (!bytes) { 
381 return NULL; 
382 } 
383 
384 qoi_write_32(bytes, p: &p, QOI_MAGIC); 
385 qoi_write_32(bytes, p: &p, v: desc->width); 
386 qoi_write_32(bytes, p: &p, v: desc->height); 
387 bytes[p++] = desc->channels; 
388 bytes[p++] = desc->colorspace; 
389 
390 
391 pixels = (const unsigned char *)data; 
392 
393 QOI_ZEROARR(index); 
394 
395 run = 0; 
396 px_prev.rgba.r = 0; 
397 px_prev.rgba.g = 0; 
398 px_prev.rgba.b = 0; 
399 px_prev.rgba.a = 255; 
400 px = px_prev; 
401 
402 px_len = desc->width * desc->height * desc->channels; 
403 px_end = px_len - desc->channels; 
404 channels = desc->channels; 
405 
406 for (px_pos = 0; px_pos < px_len; px_pos += channels) { 
407 px.rgba.r = pixels[px_pos + 0]; 
408 px.rgba.g = pixels[px_pos + 1]; 
409 px.rgba.b = pixels[px_pos + 2]; 
410 
411 if (channels == 4) { 
412 px.rgba.a = pixels[px_pos + 3]; 
413 } 
414 
415 if (px.v == px_prev.v) { 
416 run++; 
417 if (run == 62 || px_pos == px_end) { 
418 bytes[p++] = QOI_OP_RUN | (run - 1); 
419 run = 0; 
420 } 
421 } 
422 else { 
423 int index_pos; 
424 
425 if (run > 0) { 
426 bytes[p++] = QOI_OP_RUN | (run - 1); 
427 run = 0; 
428 } 
429 
430 index_pos = QOI_COLOR_HASH(px) % 64; 
431 
432 if (index[index_pos].v == px.v) { 
433 bytes[p++] = QOI_OP_INDEX | index_pos; 
434 } 
435 else { 
436 index[index_pos] = px; 
437 
438 if (px.rgba.a == px_prev.rgba.a) { 
439 signed char vr = px.rgba.r - px_prev.rgba.r; 
440 signed char vg = px.rgba.g - px_prev.rgba.g; 
441 signed char vb = px.rgba.b - px_prev.rgba.b; 
442 
443 signed char vg_r = vr - vg; 
444 signed char vg_b = vb - vg; 
445 
446 if ( 
447 vr > -3 && vr < 2 && 
448 vg > -3 && vg < 2 && 
449 vb > -3 && vb < 2 
450 ) { 
451 bytes[p++] = QOI_OP_DIFF | (vr + 2) << 4 | (vg + 2) << 2 | (vb + 2); 
452 } 
453 else if ( 
454 vg_r > -9 && vg_r < 8 && 
455 vg > -33 && vg < 32 && 
456 vg_b > -9 && vg_b < 8 
457 ) { 
458 bytes[p++] = QOI_OP_LUMA | (vg + 32); 
459 bytes[p++] = (vg_r + 8) << 4 | (vg_b + 8); 
460 } 
461 else { 
462 bytes[p++] = QOI_OP_RGB; 
463 bytes[p++] = px.rgba.r; 
464 bytes[p++] = px.rgba.g; 
465 bytes[p++] = px.rgba.b; 
466 } 
467 } 
468 else { 
469 bytes[p++] = QOI_OP_RGBA; 
470 bytes[p++] = px.rgba.r; 
471 bytes[p++] = px.rgba.g; 
472 bytes[p++] = px.rgba.b; 
473 bytes[p++] = px.rgba.a; 
474 } 
475 } 
476 } 
477 px_prev = px; 
478 } 
479 
480 for (i = 0; i < (int)sizeof(qoi_padding); i++) { 
481 bytes[p++] = qoi_padding[i]; 
482 } 
483 
484 *out_len = p; 
485 return bytes; 
486} 
487 
488void *qoi_decode(const void *data, int size, qoi_desc *desc, int channels) { 
489 const unsigned char *bytes; 
490 unsigned int header_magic; 
491 unsigned char *pixels; 
492 qoi_rgba_t index[64]; 
493 qoi_rgba_t px; 
494 int px_len, chunks_len, px_pos; 
495 int p = 0, run = 0; 
496 
497 if ( 
498 data == NULL || desc == NULL || 
499 (channels != 0 && channels != 3 && channels != 4) || 
500 size < QOI_HEADER_SIZE + (int)sizeof(qoi_padding) 
501 ) { 
502 return NULL; 
503 } 
504 
505 bytes = (const unsigned char *)data; 
506 
507 header_magic = qoi_read_32(bytes, p: &p); 
508 desc->width = qoi_read_32(bytes, p: &p); 
509 desc->height = qoi_read_32(bytes, p: &p); 
510 desc->channels = bytes[p++]; 
511 desc->colorspace = bytes[p++]; 
512 
513 if ( 
514 desc->width == 0 || desc->height == 0 || 
515 desc->channels < 3 || desc->channels > 4 || 
516 desc->colorspace > 1 || 
517 header_magic != QOI_MAGIC || 
518 desc->height >= QOI_PIXELS_MAX / desc->width 
519 ) { 
520 return NULL; 
521 } 
522 
523 if (channels == 0) { 
524 channels = desc->channels; 
525 } 
526 
527 px_len = desc->width * desc->height * channels; 
528 pixels = (unsigned char *) QOI_MALLOC(px_len); 
529 if (!pixels) { 
530 return NULL; 
531 } 
532 
533 QOI_ZEROARR(index); 
534 px.rgba.r = 0; 
535 px.rgba.g = 0; 
536 px.rgba.b = 0; 
537 px.rgba.a = 255; 
538 
539 chunks_len = size - (int)sizeof(qoi_padding); 
540 for (px_pos = 0; px_pos < px_len; px_pos += channels) { 
541 if (run > 0) { 
542 run--; 
543 } 
544 else if (p < chunks_len) { 
545 int b1 = bytes[p++]; 
546 
547 if (b1 == QOI_OP_RGB) { 
548 px.rgba.r = bytes[p++]; 
549 px.rgba.g = bytes[p++]; 
550 px.rgba.b = bytes[p++]; 
551 } 
552 else if (b1 == QOI_OP_RGBA) { 
553 px.rgba.r = bytes[p++]; 
554 px.rgba.g = bytes[p++]; 
555 px.rgba.b = bytes[p++]; 
556 px.rgba.a = bytes[p++]; 
557 } 
558 else if ((b1 & QOI_MASK_2) == QOI_OP_INDEX) { 
559 px = index[b1]; 
560 } 
561 else if ((b1 & QOI_MASK_2) == QOI_OP_DIFF) { 
562 px.rgba.r += ((b1 >> 4) & 0x03) - 2; 
563 px.rgba.g += ((b1 >> 2) & 0x03) - 2; 
564 px.rgba.b += ( b1 & 0x03) - 2; 
565 } 
566 else if ((b1 & QOI_MASK_2) == QOI_OP_LUMA) { 
567 int b2 = bytes[p++]; 
568 int vg = (b1 & 0x3f) - 32; 
569 px.rgba.r += vg - 8 + ((b2 >> 4) & 0x0f); 
570 px.rgba.g += vg; 
571 px.rgba.b += vg - 8 + (b2 & 0x0f); 
572 } 
573 else if ((b1 & QOI_MASK_2) == QOI_OP_RUN) { 
574 run = (b1 & 0x3f); 
575 } 
576 
577 index[QOI_COLOR_HASH(px) % 64] = px; 
578 } 
579 
580 pixels[px_pos + 0] = px.rgba.r; 
581 pixels[px_pos + 1] = px.rgba.g; 
582 pixels[px_pos + 2] = px.rgba.b; 
583  
584 if (channels == 4) { 
585 pixels[px_pos + 3] = px.rgba.a; 
586 } 
587 } 
588 
589 return pixels; 
590} 
591 
592#ifndef QOI_NO_STDIO 
593#include <stdio.h> 
594 
595int qoi_write(const char *filename, const void *data, const qoi_desc *desc) { 
596 FILE *f = fopen(filename, "wb"); 
597 int size; 
598 void *encoded; 
599 
600 if (!f) { 
601 return 0; 
602 } 
603 
604 encoded = qoi_encode(data, desc, &size); 
605 if (!encoded) { 
606 fclose(f); 
607 return 0; 
608 } 
609 
610 fwrite(encoded, 1, size, f); 
611 fclose(f); 
612 
613 QOI_FREE(encoded); 
614 return size; 
615} 
616 
617void *qoi_read(const char *filename, qoi_desc *desc, int channels) { 
618 FILE *f = fopen(filename, "rb"); 
619 int size, bytes_read; 
620 void *pixels, *data; 
621 
622 if (!f) { 
623 return NULL; 
624 } 
625 
626 fseek(f, 0, SEEK_END); 
627 size = ftell(f); 
628 if (size <= 0) { 
629 fclose(f); 
630 return NULL; 
631 } 
632 fseek(f, 0, SEEK_SET); 
633 
634 data = QOI_MALLOC(size); 
635 if (!data) { 
636 fclose(f); 
637 return NULL; 
638 } 
639 
640 bytes_read = fread(data, 1, size, f); 
641 fclose(f); 
642 
643 pixels = qoi_decode(data, bytes_read, desc, channels); 
644 QOI_FREE(data); 
645 return pixels; 
646} 
647 
648#endif /* QOI_NO_STDIO */ 
649#endif /* QOI_IMPLEMENTATION */ 
650