Skip to content

Instantly share code, notes, and snippets.

@pkhuong
pkhuong / yannakakis.md
Last active April 13, 2024 14:36
A minimal version of Yannakakis's algorithm for mostly plain Python
#!/usr/bin/env sed -re s|^|\x20\x20\x20\x20| -e s|^\x20{4}\x23\x23{(.*)$|<details><summary>\1</summary>\n| -e s|^\x20{4}\x23\x23}$|\n</details>| -e s|^\x20{4}\x23\x23\x20?|| -e s|\x0c|\x20|
license, imports
# Yannakakis.py by Paul Khuong
#
# To the extent possible under law, the person who associated CC0 with
# Yannakakis.py has waived all copyright and related or neighboring rights
# to Yannakakis.py.

// Merge pass
static void merge_pass(S16 *out, const S16 *inA, const S16 *inB, size_t elemsPerRun)
{
// need pow2 elemsPerRun>=16!
const S16 *endA = inA + elemsPerRun;
const S16 *endB = inB + elemsPerRun;
Vec vMin0 = load8_s16(inA + 0);
Vec vMin1 = load8_s16(inA + 8);
Vec vMax0 = load8_s16(inB + 0);
Vec vMax1 = load8_s16(inB + 8);
@MarkMendell
MarkMendell / grapheme.c
Last active February 17, 2024 06:19
Code for extended grapheme cluster breaks
// Public domain
#include <stddef.h>
#include <stdint.h>
#if 0
// Example program
int
getlenextendedgrapheme(size_t nbuf, uint8_t *buf, size_t i)
{
#include <stdint.h>
typedef unsigned char U8;
typedef unsigned short U16;
typedef unsigned int U32;
typedef unsigned long long U64;
typedef intptr_t SINTa;
struct KernelState
{
@rygorous
rygorous / rast.c
Created March 2, 2020 01:56
Simple watertight triangle rasterizer
// ---- triangle rasterizer
#define SUBPIXEL_SHIFT 8
#define SUBPIXEL_SCALE (1 << SUBPIXEL_SHIFT)
static RADINLINE S64 det2x2(S32 a, S32 b, S32 c, S32 d)
{
S64 r = (S64) a*d - (S64) b*c;
return r >> SUBPIXEL_SHIFT;
}
// Baseline version without prefetch
static const LRMEntry * lrm_search_one_basic(const LRM * lrm, const U8 * ptr)
{
LRM_hash_t hash = lrm_hash8(ptr);
// Jump-in: narrow down the search interval using the jump table
LRM_hash_t ji = hash >> lrm->jumpInShift;
S32 jump1 = lrm->jumpIn[ji];
S32 jump2 = lrm->jumpIn[ji + 1];
@schellingb
schellingb / my default.vcxproj
Last active May 22, 2022 17:32
A short and readable single .vcxproj file that opens and builds in Visual Studio 2012, 2013, 2015, 2017 and 2019 with good default settings.
<?xml version="1.0" encoding="utf-8"?>
<Project DefaultTargets="Build" ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003" InitialTargets="DisplayText">
<PropertyGroup Label="UserMacros">
<VisualStudioYear Condition="'$(VisualStudioVersion)' == '11.0' Or '$(PlatformToolsetVersion)' == '110' Or '$(MSBuildToolsVersion)' == '4.0'">2012</VisualStudioYear>
<VisualStudioYear Condition="'$(VisualStudioVersion)' == '12.0' Or '$(PlatformToolsetVersion)' == '120' Or '$(MSBuildToolsVersion)' == '12.0'">2013</VisualStudioYear>
<VisualStudioYear Condition="'$(VisualStudioVersion)' == '14.0' Or '$(PlatformToolsetVersion)' == '140' Or '$(MSBuildToolsVersion)' == '14.0'">2015</VisualStudioYear>
<VisualStudioYear Condition="'$(VisualStudioVersion)' == '15.0' Or '$(PlatformToolsetVersion)' == '141' Or '$(MSBuildToolsVersion)' == '15.0'">2017</VisualStudioYear>
<VisualStudioYear Condition="'$(VisualStudioVersion)' == '16.0' Or '$(PlatformToolsetVersion)' == '142' Or '$(MSBuildTo
@rygorous
rygorous / mergesort_kit.cpp
Last active August 28, 2023 10:13
int16 mergesort construction kit
#include <emmintrin.h>
#include <tmmintrin.h> // for PSHUFB; this isn't strictly necessary (see comments in reverse_s16)
typedef int16_t S16;
typedef __m128i Vec;
static inline Vec load8_s16(const S16 *x) { return _mm_loadu_si128((const __m128i *) x); }
static inline void store8_s16(S16 *x, Vec v) { _mm_storeu_si128((__m128i *) x, v); }
static inline void sort_two(Vec &a, Vec &b) { Vec t = a; a = _mm_min_epi16(a, b); b = _mm_max_epi16(b, t); }
@rygorous
rygorous / hb_stb_truetype.c
Last active October 31, 2023 00:45
HarfBuzz->stb_truetype
// ---- loading a font
static void load_font(void)
{
hb_blob_t *blob;
hb_face_t *face;
size_t filelen = 0;
void *filedata = stb_file("c:/windows/fonts/arial.ttf", &filelen);
if (filedata == 0) stbpg_fatal("Couldn't load font");