<commit_before>/*
	Blur grayscale demo, including MMX implementation. $Revision: 1.14 $

	Algorithm used here is described on my website (polish only).
	
	In short words: this is simple (and well known) average
	of 9 neighbour pixels.  However I've realized that
	blurring adjacent pixels (and scanlines) require fewer
	pixels fetches and fewer additions, because we can reuse
	some pixels fetched in previous iterations and partial
	sums calculated already.

	Define USE_Xscr symbol to compile interactive version.
	Xscr and load_ppm [tiny] libraries are available on my website,
	look at http://0x80.pl/snippets/ and http://0x80.pl/proj/.


	Author: <NAME>
	e-mail: <EMAIL>
	www:    http://0x80.pl/
	
	License: BSD
	
	initial release 14-07-2007, last update $Date: 2008-06-08 23:00:44 $
*/

#ifndef _XOPEN_SOURCE
#	define _XOPEN_SOURCE 600
#endif

#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <strings.h>

#define SUM_TABLE_SIZE		(1024*16)
#define MAX_GRAY_WIDTH		SUM_TABLE_SIZE
#define MAX_32bpp_WIDTH		(SUM_TABLE_SIZE/4)

uint16_t SUM_TABLE[3*SUM_TABLE_SIZE]__attribute__((aligned (16)));

uint8_t divide_lookup[255*9 + 1]; // sum \in [0..9*255]

void initialize_divide_lookup() {
	unsigned int i;
	for (i=0; i < sizeof(divide_lookup); i++)
		// divide_lookup[i] = i/9;
		divide_lookup[i] = (i * (65536/9) + (65536/9)) >> 16;
}

#define inlinefun __attribute__ ((always_inline))


// C-language implementation

void inlinefun
blur_gray_calc_sums(
	uint8_t  *src_img,
	uint8_t  border_color,
	uint16_t *sum_tbl,
	unsigned int width
) {
	int x;
	uint8_t *pix;
	uint16_t a, b, c;

	pix = src_img;
	a = border_color;
	b = *pix++;
	for (x=0; x < width-1; x++) {
		c = *pix++;
		sum_tbl[x] = a + b + c;
		a = b;
		b = c;
	}

	c = border_color;
	sum_tbl[width-1] = a + b + c;
}


void inlinefun
blur_gray_calc_avg(uint8_t *dst_img, unsigned int width) {
	unsigned int x;
	uint8_t *pix;
	uint16_t *sum;

	pix = dst_img;
	sum = SUM_TABLE;
	for (x=0; x < width; x++)
		*pix++ = divide_lookup[
			SUM_TABLE[x + 0*SUM_TABLE_SIZE] +
			SUM_TABLE[x + 1*SUM_TABLE_SIZE] +
			SUM_TABLE[x + 2*SUM_TABLE_SIZE]
		];
}



// x86 implementation

void inlinefun
x86blur_gray_calc_sums(
	uint8_t  *src_img,
	uint8_t   border_color,
	uint16_t *sum_tbl,
	unsigned int width
) {
	uint32_t dummy __attribute__((unused));

	__asm__ volatile (
	    // eax = border_color
	"   pushl %%eax                           \n\t"
	"   xorl %%ebx, %%ebx                     \n\t"
	"   xorl %%ecx, %%ecx                     \n\t"
	"                                         \n\t"
	"   movb (%%esi), %%bl                    \n\t" // b = pix[0]
	"   addl $1, %%esi                        \n\t"
	"                                         \n\t"
	"0:                                       \n\t"
	"   movb (%%esi), %%cl                    \n\t" // c = pix[x+1]
	"   addl %%ebx, %%eax                     \n\t" // a += b
	"   addl $1, %%esi                        \n\t" // pix++;
	"   addl %%ecx, %%eax                     \n\t" // a += c
	"                                         \n\t"
	"   movw %%ax, (%%edi)                    \n\t" // sum_tbl[x] = a
	"   movl %%ebx, %%eax                     \n\t" // a = b
	"   movl %%ecx, %%ebx                     \n\t" // b = c
	"                                         \n\t"
	"   addl $2, %%edi                        \n\t" // x++;
	"   subl $1, %%edx                        \n\t"
	"   jnz  0b                               \n\t"
	"                                         \n\t"
	"   popl %%ecx                            \n\t"
	"   add  %%ebx, %%eax                     \n\t"
	"   add  %%ecx, %%eax                     \n\t"
	"                                         \n\t"
	"   movw %%ax, (%%edi)                    \n\t"
	
	: "=S" (dummy), "=D" (dummy), "=d" (dummy), "=a" (dummy)
	: "S" (src_img), "D" (sum_tbl), "d" (width-1), "a" (border_color)
	: "%ebx", "%ecx", "memory"
	);
}

void inlinefun
x86blur_gray_calc_avg(uint8_t *dst_img, unsigned int width) {
	uint32_t dummy __attribute__((unused));

	__asm__ volatile (
	"0:                                       \n\t"
	"   xorl %%eax, %%eax                     \n\t"
	"   movw         (%%esi), %%ax            \n\t" // ax  = SUM_TABLE[i]
	"   addw %c[ofs1](%%esi), %%ax            \n\t" // ax += SUM_TABLE[i + SUM_TABLE_SIZE]
	"   addw %c[ofs2](%%esi), %%ax            \n\t"	// ax += SUM_TABLE[i + 2*SUM_TABLE_SIZE]
	
	"   movb %c[dtbl](%%eax), %%al            \n\t" // bl = divide_lookup[ax]
	"   movb %%al, (%%edi)                    \n\t" // dst_img <- bl
	"                                         \n\t"
	"   addl $2, %%esi                        \n\t"
	"   addl $1, %%edi                        \n\t"
	"                                         \n\t"
	"   decl %%edx                            \n\t"
	"   jnz 0b                                \n\t"
	"                                         \n\t"
	: "=S" (dummy), "=D" (dummy), "=d" (dummy)
	: [ofs1] "e" (2*SUM_TABLE_SIZE), // SUM_TABLE + SUM_TABLE_SIZE
	  [ofs2] "e" (4*SUM_TABLE_SIZE), // SUM_TABLE + 2*SUM_TABLE_SIZE
	  [dtbl] "e" (divide_lookup),    // divtable address
	  "S" (SUM_TABLE), "D" (dst_img), "d" (width)
	: "%eax", "memory"
	);
}


// MMX implementation

void inlinefun
mmxblur_gray_calc_sums(
	uint8_t  *src_img,
	uint8_t   border_color,
	uint16_t *sum_tbl,
	unsigned int width
) {
	uint32_t dummy __attribute__((unused));

	__asm__ volatile(
	"   pxor %%mm7, %%mm7                     \n\t"
	"0:                                       \n\t"
	"   movq 0(%%esi), %%mm0                  \n\t"
	"   movq 1(%%esi), %%mm1                  \n\t"
	"   movq 2(%%esi), %%mm2                  \n\t"
	"                                         \n\t"
	"   movq %%mm0, %%mm3                     \n\t"
	"   movq %%mm1, %%mm4                     \n\t"
	"   movq %%mm2, %%mm5                     \n\t"
	"                                         \n\t"
	"   punpcklbw %%mm7, %%mm0                \n\t"
	"   punpcklbw %%mm7, %%mm1                \n\t"
	"   punpcklbw %%mm7, %%mm2                \n\t"
	"                                         \n\t"
	"   punpckhbw %%mm7, %%mm3                \n\t"
	"   punpckhbw %%mm7, %%mm4                \n\t"
	"   punpckhbw %%mm7, %%mm5                \n\t"
	"                                         \n\t"
	"   paddw %%mm1, %%mm0                    \n\t"
	"   paddw %%mm2, %%mm0                    \n\t"
	"                                         \n\t"
	"   paddw %%mm4, %%mm3                    \n\t"
	"   paddw %%mm5, %%mm3                    \n\t"
	"                                         \n\t"
	"   movq %%mm0,  0(%%edi)                 \n\t"
	"   movq %%mm3,  8(%%edi)                 \n\t"
	"                                         \n\t"
	"   addl $8,  %%esi                       \n\t"
	"   addl $16, %%edi                       \n\t"
	"                                         \n\t"
	"   subl $1, %%ecx                        \n\t"
	"   jnz  0b                               \n\t"
	"                                         \n\t"
	: "=S" (dummy), "=D" (dummy), "=c" (dummy)
	: "S" (src_img), "D" (sum_tbl+1), "c" (width/8)
	: "memory"
	);

	// fix sum for first pixel:
	sum_tbl[0]  = sum_tbl[1];
	sum_tbl[0] -= (uint16_t)src_img[0];
	sum_tbl[0] += (uint16_t)border_color;
	
	// fix sum for last pixel:
	sum_tbl[width] -= (uint16_t)src_img[width];
	sum_tbl[width] += (uint16_t)border_color;
}

// MMX[2] implementation

void inlinefun
mmx2blur_gray_calc_sums(
	uint8_t  *src_img,
	uint8_t   border_color,
	uint16_t *sum_tbl,
	unsigned int width
) {
	uint32_t dummy __attribute__((unused));

	__asm__ volatile(
	"   pxor %%mm7, %%mm7                     \n\t"
	"   movq 0(%%esi), %%mm6                  \n\t"
	"0:                                       \n\t"
	"   movq %%mm6, %%mm0                     \n\t"
	"   movq 8(%%esi), %%mm3                  \n\t"
	"   movq %%mm3, %%mm6                     \n\t"
	"                                         \n\t"
	"   movq %%mm0, %%mm1                     \n\t"
	"   movq %%mm0, %%mm2                     \n\t"
	"   movq %%mm3, %%mm4                     \n\t"
	"                                         \n\t"
	"   psrlq  $8, %%mm1                      \n\t"
	"   psrlq $16, %%mm2                      \n\t"
	"   psllq $56, %%mm3                      \n\t"
	"   psllq $48, %%mm4                      \n\t"
	"                                         \n\t"
	"   por %%mm3, %%mm1                      \n\t"
	"   por %%mm4, %%mm2                      \n\t"
	"                                         \n\t"
	"   movq %%mm0, %%mm3                     \n\t"
	"   movq %%mm1, %%mm4                     \n\t"
	"   movq %%mm2, %%mm5                     \n\t"
	"                                         \n\t"
	"   punpcklbw %%mm7, %%mm0                \n\t"
	"   punpcklbw %%mm7, %%mm1                \n\t"
	"   punpcklbw %%mm7, %%mm2                \n\t"
	"                                         \n\t"
	"   punpckhbw %%mm7, %%mm3                \n\t"
	"   punpckhbw %%mm7, %%mm4                \n\t"
	"   punpckhbw %%mm7, %%mm5                \n\t"
	"                                         \n\t"
	"   paddw %%mm1, %%mm0                    \n\t"
	"   paddw %%mm2, %%mm0                    \n\t"
	"                                         \n\t"
	"   paddw %%mm4, %%mm3                    \n\t"
	"   paddw %%mm5, %%mm3                    \n\t"
	"                                         \n\t"
	"   movq %%mm0,  0(%%edi)                 \n\t"
	"   movq %%mm3,  8(%%edi)                 \n\t"
	"                                         \n\t"
	"   addl $8,  %%esi                       \n\t"
	"   addl $16, %%edi                       \n\t"
	"                                         \n\t"
	"   subl $1, %%ecx                        \n\t"
	"   jnz  0b                               \n\t"
	"                                         \n\t"
	: "=S" (dummy), "=D" (dummy), "=c" (dummy)
	: "S" (src_img), "D" (sum_tbl), "c" (width/8)
	: "memory"
	);
<commit_msg>minor updates<commit_after>/*
	What is it?
	------------------------------------------------------------------------

	Blur grayscale demo, including MMX implementation.

	Algorithm used here is described on my website (polish only).
	
	In short words: this is simple (and well known) average
	of 9 neighbour pixels.  However I've realized that
	blurring adjacent pixels (and scanlines) require fewer
	pixels fetches and fewer additions, because we can reuse
	some pixels fetched in previous iterations and partial
	sums calculated already.

	Compilation
	------------------------------------------------------------------------

	simple test program:

	$ gcc -O2 saturated_add.c -o program


	X11 view program

	$ gcc -IXscr -Iloadppm -DUSE_Xscr saturated_add.c Xscr/Xscr.c loadppm/load_ppm.c -lX11 -o program

	Additional libraries are available at github:
	* https://github.com/WojciechMula/Xscr
	* https://github.com/WojciechMula/loadppm


	Usage
	------------------------------------------------------------------------

	Run program without arguments to read help.


	Author: <NAME>
	e-mail: <EMAIL>
	www:    http://0x80.pl/
	
	License: BSD
	
	initial release: 2007-07-14
	         update: 2008-06-08
	         update: 2013-10-06 - fixed MMX2
*/

#ifndef _XOPEN_SOURCE
#	define _XOPEN_SOURCE 600
#endif

#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <strings.h>

#define SUM_TABLE_SIZE		(1024*16)
#define MAX_GRAY_WIDTH		SUM_TABLE_SIZE
#define MAX_32bpp_WIDTH		(SUM_TABLE_SIZE/4)

uint16_t SUM_TABLE[3*SUM_TABLE_SIZE]__attribute__((aligned (16)));

uint8_t divide_lookup[255*9 + 1]; // sum \in [0..9*255]

void initialize_divide_lookup() {
	unsigned int i;
	for (i=0; i < sizeof(divide_lookup); i++)
		// divide_lookup[i] = i/9;
		divide_lookup[i] = (i * (65536/9) + (65536/9)) >> 16;
}

#define inlinefun __attribute__ ((always_inline))


// C-language implementation

void inlinefun
blur_gray_calc_sums(
	uint8_t  *src_img,
	uint8_t  border_color,
	uint16_t *sum_tbl,
	unsigned int width
) {
	int x;
	uint8_t *pix;
	uint16_t a, b, c;

	pix = src_img;
	a = border_color;
	b = *pix++;
	for (x=0; x < width-1; x++) {
		c = *pix++;
		sum_tbl[x] = a + b + c;
		a = b;
		b = c;
	}

	c = border_color;
	sum_tbl[width-1] = a + b + c;
}


void inlinefun
blur_gray_calc_avg(uint8_t *dst_img, unsigned int width) {
	unsigned int x;
	uint8_t *pix;
	uint16_t *sum;

	pix = dst_img;
	sum = SUM_TABLE;
	for (x=0; x < width; x++)
		*pix++ = divide_lookup[
			SUM_TABLE[x + 0*SUM_TABLE_SIZE] +
			SUM_TABLE[x + 1*SUM_TABLE_SIZE] +
			SUM_TABLE[x + 2*SUM_TABLE_SIZE]
		];
}



// x86 implementation

void inlinefun
x86blur_gray_calc_sums(
	uint8_t  *src_img,
	uint8_t   border_color,
	uint16_t *sum_tbl,
	unsigned int width
) {
	uint32_t dummy __attribute__((unused));

	__asm__ volatile (
	    // eax = border_color
	"   pushl %%eax                           \n\t"
	"   xorl %%ebx, %%ebx                     \n\t"
	"   xorl %%ecx, %%ecx                     \n\t"
	"                                         \n\t"
	"   movb (%%esi), %%bl                    \n\t" // b = pix[0]
	"   addl $1, %%esi                        \n\t"
	"                                         \n\t"
	"0:                                       \n\t"
	"   movb (%%esi), %%cl                    \n\t" // c = pix[x+1]
	"   addl %%ebx, %%eax                     \n\t" // a += b
	"   addl $1, %%esi                        \n\t" // pix++;
	"   addl %%ecx, %%eax                     \n\t" // a += c
	"                                         \n\t"
	"   movw %%ax, (%%edi)                    \n\t" // sum_tbl[x] = a
	"   movl %%ebx, %%eax                     \n\t" // a = b
	"   movl %%ecx, %%ebx                     \n\t" // b = c
	"                                         \n\t"
	"   addl $2, %%edi                        \n\t" // x++;
	"   subl $1, %%edx                        \n\t"
	"   jnz  0b                               \n\t"
	"                                         \n\t"
	"   popl %%ecx                            \n\t"
	"   add  %%ebx, %%eax                     \n\t"
	"   add  %%ecx, %%eax                     \n\t"
	"                                         \n\t"
	"   movw %%ax, (%%edi)                    \n\t"
	
	: "=S" (dummy), "=D" (dummy), "=d" (dummy), "=a" (dummy)
	: "S" (src_img), "D" (sum_tbl), "d" (width-1), "a" (border_color)
	: "%ebx", "%ecx", "memory"
	);
}

void inlinefun
x86blur_gray_calc_avg(uint8_t *dst_img, unsigned int width) {
	uint32_t dummy __attribute__((unused));

	__asm__ volatile (
	"0:                                       \n\t"
	"   xorl %%eax, %%eax                     \n\t"
	"   movw         (%%esi), %%ax            \n\t" // ax  = SUM_TABLE[i]
	"   addw %c[ofs1](%%esi), %%ax            \n\t" // ax += SUM_TABLE[i + SUM_TABLE_SIZE]
	"   addw %c[ofs2](%%esi), %%ax            \n\t"	// ax += SUM_TABLE[i + 2*SUM_TABLE_SIZE]
	
	"   movb %c[dtbl](%%eax), %%al            \n\t" // bl = divide_lookup[ax]
	"   movb %%al, (%%edi)                    \n\t" // dst_img <- bl
	"                                         \n\t"
	"   addl $2, %%esi                        \n\t"
	"   addl $1, %%edi                        \n\t"
	"                                         \n\t"
	"   decl %%edx                            \n\t"
	"   jnz 0b                                \n\t"
	"                                         \n\t"
	: "=S" (dummy), "=D" (dummy), "=d" (dummy)
	: [ofs1] "e" (2*SUM_TABLE_SIZE), // SUM_TABLE + SUM_TABLE_SIZE
	  [ofs2] "e" (4*SUM_TABLE_SIZE), // SUM_TABLE + 2*SUM_TABLE_SIZE
	  [dtbl] "e" (divide_lookup),    // divtable address
	  "S" (SUM_TABLE), "D" (dst_img), "d" (width)
	: "%eax", "memory"
	);
}


// MMX implementation

void inlinefun
mmxblur_gray_calc_sums(
	uint8_t  *src_img,
	uint8_t   border_color,
	uint16_t *sum_tbl,
	unsigned int width
) {
	uint32_t dummy __attribute__((unused));

	__asm__ volatile(
	"   pxor %%mm7, %%mm7                     \n\t"
	"0:                                       \n\t"
	"   movq 0(%%esi), %%mm0                  \n\t"
	"   movq 1(%%esi), %%mm1                  \n\t"
	"   movq 2(%%esi), %%mm2                  \n\t"
	"                                         \n\t"
	"   movq %%mm0, %%mm3                     \n\t"
	"   movq %%mm1, %%mm4                     \n\t"
	"   movq %%mm2, %%mm5                     \n\t"
	"                                         \n\t"
	"   punpcklbw %%mm7, %%mm0                \n\t"
	"   punpcklbw %%mm7, %%mm1                \n\t"
	"   punpcklbw %%mm7, %%mm2                \n\t"
	"                                         \n\t"
	"   punpckhbw %%mm7, %%mm3                \n\t"
	"   punpckhbw %%mm7, %%mm4                \n\t"
	"   punpckhbw %%mm7, %%mm5                \n\t"
	"                                         \n\t"
	"   paddw %%mm1, %%mm0                    \n\t"
	"   paddw %%mm2, %%mm0                    \n\t"
	"                                         \n\t"
	"   paddw %%mm4, %%mm3                    \n\t"
	"   paddw %%mm5, %%mm3                    \n\t"
	"                                         \n\t"
	"   movq %%mm0,  0(%%edi)                 \n\t"
	"   movq %%mm3,  8(%%edi)                 \n\t"
	"                                         \n\t"
	"   addl $8,  %%esi                       \n\t"
	"   addl $16, %%edi                       \n\t"
	"                                         \n\t"
	"   subl $1, %%ecx                        \n\t"
	"   jnz  0b                               \n\t"
	"                                         \n\t"
	: "=S" (dummy), "=D" (dummy), "=c" (dummy)
	: "S" (src_img), "D" (sum_tbl+1), "c" (width/8)
	: "memory"
	);

	// fix sum for first pixel:
	sum_tbl[0]  = sum_tbl[1];
	sum_tbl[0] -= (uint16_t)src_img[0];
	sum_tbl[0] += (uint16_t)border_color;
	
	// fix sum for last pixel:
	sum_tbl[width] -= (uint16_t)src_img[width];
	sum_tbl[width] += (uint16_t)border_color;
}

// MMX[2] implementation

void inlinefun
mmx2blur_gray_calc_sums(
	uint8_t  *src_img,
	uint8_t   border_color,
	uint16_t *sum_tbl,
	unsigned int width
) {
	uint32_t dummy __attribute__((unused));

	__asm__ volatile(
	"   pxor %%mm7, %%mm7                     \n\t"
	"   movq 0(%%esi), %%mm6                  \n\t"
	"0:                                       \n\t"
	"   movq %%mm6, %%mm0                     \n\t"
	"   movq 8(%%esi), %%mm3                  \n\t"
	"   movq %%mm3, %%mm6                     \n\t"
	"                                         \n\t"
	"   movq %%mm0, %%mm1                     \n\t"
	"   movq %%mm0, %%mm2                     \n\t"
	"   movq %%mm3, %%mm4                     \n\t"
	"                                         \n\t"
	"   psrlq  $8, %%mm1                      \n\t"
	"   psrlq $16, %%mm2                      \n\t"
	"   psllq $56, %%mm3                      \n\t"
	"   psllq $48, %%mm4                      \n\t"
	"                                         \n\t"
	"   por %%mm3, %%mm1                      \n\t"
	"   por %%mm4, %%mm2                      \n\t"
	"                                         \n\t"
	"   movq %%mm0, %%mm3                     \n\t"
	"   movq %%mm1, %%mm4                     \n\t"
	"   movq %%mm2, %%mm5                     \n\t"
	"                                         \n\t"
	"   punpcklbw %%mm7, %%mm0                \n\t"
	"   punpcklbw %%mm7, %%mm1                \n\t"
	"   punpcklbw %%mm7, %%mm2                \n\t"
	"                                         \n\t"
	"   punpckhbw %%mm7, %%mm3                \n\t"
	"   punpckhbw %%mm7, %%mm4                \n\t"
	"   punpckhbw %%mm7, %%mm5                \n\t"
	"                                         \n\t"
	"   paddw %%mm1, %%mm0                    \n\t"
	"   paddw %%mm2, %%mm0                    \n\t"
	"                                         \n\t"
	"   paddw %%mm4, %%mm3                    \n\t"
	"   paddw %%mm5, %%mm3                    \n\t"
	"                                         \n\t"
	"   movq %%mm0,  0(%%edi)                 \n\t"
	"   movq %%mm3,  8(%%edi)                 \n\t"
	"                                         \n\t"
	"   addl $8,  %%esi                       \n\t"
	"   addl $16, %%edi                       \n\t"
	"                                         \n\t"
	"   subl $1, %%ecx                        \n\t"
	"   jnz  0b                               \n\t"
	"                                         \n\t"
	: "=S" (dummy), "=D" (dummy), "=c" (dummy)
	: "S" (src_img), "D" (sum_tbl+1), "c" (width/8)
	: "memory"
	);

{'fraction_non_alphanumeric': 0.1645078991266804, 'fraction_numerical': 0.026886468452556177, 'mean_word_length': 1.0263445670543792, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 19, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 136, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '24893', 'n_tokens_mistral': 8185, 'n_tokens_neox': 7396, 'n_words': 1617}