From 1b991a54cc834e8ef9ccc8bb15dce7ff70cdf8a3 Mon Sep 17 00:00:00 2001 From: Sadeep Madurange Date: Wed, 24 Dec 2025 16:29:32 +0800 Subject: Matrix post. --- _log/_site/arduino-due.html | 109 +++++++++ _log/_site/arduino-due/connections.jpeg | Bin 0 -> 29090 bytes _log/_site/arduino-due/schematic.png | Bin 0 -> 68688 bytes _log/_site/arduino-due/source.tar.gz | Bin 0 -> 1174 bytes _log/_site/arduino-uno.html | 76 +++++++ _log/_site/arduino-uno/3v3.Makefile | 46 ++++ _log/_site/arduino-uno/Makefile | 43 ++++ _log/_site/arduino-uno/breadboard.jpeg | Bin 0 -> 54319 bytes _log/_site/arduino-uno/pinout.png | Bin 0 -> 247197 bytes _log/_site/bumblebee.html | 40 ++++ _log/_site/bumblebee/bee.mp4 | Bin 0 -> 2352029 bytes _log/_site/bumblebee/poster.png | Bin 0 -> 18024 bytes _log/_site/bumblebee/thumb_sm.png | Bin 0 -> 6189 bytes _log/_site/e-reader.html | 85 +++++++ _log/_site/e-reader/circuit.svg | 145 ++++++++++++ _log/_site/e-reader/ereader.mp4 | Bin 0 -> 3101166 bytes _log/_site/e-reader/poster.png | Bin 0 -> 674187 bytes _log/_site/e-reader/source.tar.gz | Bin 0 -> 14304 bytes _log/_site/e-reader/thumb_sm.png | Bin 0 -> 240117 bytes _log/_site/etlas.html | 103 +++++++++ _log/_site/etlas/circuit.svg | 105 +++++++++ _log/_site/etlas/dash.jpg | Bin 0 -> 85874 bytes _log/_site/etlas/etlas_arch.png | Bin 0 -> 47732 bytes _log/_site/etlas/pcb.jpg | Bin 0 -> 75769 bytes _log/_site/etlas/schematic.svg | 4 + _log/_site/etlas/source.tar.gz | Bin 0 -> 46871 bytes _log/_site/etlas/thumb_sm.jpg | Bin 0 -> 55678 bytes _log/_site/feed.xml | 1 + _log/_site/fpm-door-lock.html | 105 +++++++++ _log/_site/fpm-door-lock/breadboard.jpg | Bin 0 -> 46771 bytes _log/_site/fpm-door-lock/footprint.png | Bin 0 -> 198127 bytes _log/_site/fpm-door-lock/gerber.zip | Bin 0 -> 89431 bytes _log/_site/fpm-door-lock/pcb.jpg | Bin 0 -> 68237 bytes _log/_site/fpm-door-lock/pcb1.jpg | Bin 0 -> 37068 bytes _log/_site/fpm-door-lock/source.tar.gz | Bin 0 -> 29473 bytes _log/_site/fpm-door-lock/thumb_sm.jpg | Bin 0 -> 18380 bytes _log/_site/fpm-door-lock/video.mp4 | Bin 0 -> 13264594 bytes _log/_site/matrix-digital-rain.html | 103 +++++++++ _log/_site/matrix-digital-rain/katakana.png | Bin 0 -> 133709 bytes _log/_site/matrix-digital-rain/matrix.mp4 | Bin 0 -> 696574 bytes _log/_site/matrix-digital-rain/poster.png | Bin 0 -> 233077 bytes _log/_site/matrix-digital-rain/source.tar.gz | Bin 0 -> 3602 bytes _log/_site/matrix-digital-rain/thumb_sm.png | Bin 0 -> 52762 bytes _log/_site/mosfet-switches.html | 110 ++++++++++ _log/_site/mosfet-switches/bjt.png | Bin 0 -> 12838 bytes _log/_site/mosfet-switches/n_high_side.png | Bin 0 -> 10825 bytes _log/_site/mosfet-switches/p_high_side.png | Bin 0 -> 10724 bytes _log/_site/my-first-pcb.html | 57 +++++ _log/_site/my-first-pcb/back.jpeg | Bin 0 -> 34023 bytes _log/_site/my-first-pcb/back_design.jpeg | Bin 0 -> 31946 bytes _log/_site/my-first-pcb/front.jpeg | Bin 0 -> 28997 bytes _log/_site/my-first-pcb/front_design.jpeg | Bin 0 -> 32174 bytes _log/_site/my-first-pcb/gerber_back.zip | Bin 0 -> 48217 bytes _log/_site/my-first-pcb/gerber_front.zip | Bin 0 -> 49605 bytes _log/_site/my-first-pcb/source.tar.gz | Bin 0 -> 6660 bytes _log/_site/my-first-pcb/thumb_sm.jpeg | Bin 0 -> 6181 bytes _log/_site/neo4j-a-star-search.html | 307 ++++++++++++++++++++++++++ _log/_site/robots.txt | 1 + _log/_site/sitemap.xml | 36 +++ _log/_site/suckless-software.html | 78 +++++++ _log/matrix-digital-rain.md | 127 ++++++----- _log/my-first-pcb.md | 1 - _log/neo4j-a-star-search.md | 317 +++++++++++++++++++++++++++ 63 files changed, 1934 insertions(+), 65 deletions(-) create mode 100644 _log/_site/arduino-due.html create mode 100644 _log/_site/arduino-due/connections.jpeg create mode 100644 _log/_site/arduino-due/schematic.png create mode 100644 _log/_site/arduino-due/source.tar.gz create mode 100644 _log/_site/arduino-uno.html create mode 100644 _log/_site/arduino-uno/3v3.Makefile create mode 100644 _log/_site/arduino-uno/Makefile create mode 100644 _log/_site/arduino-uno/breadboard.jpeg create mode 100644 _log/_site/arduino-uno/pinout.png create mode 100644 _log/_site/bumblebee.html create mode 100644 _log/_site/bumblebee/bee.mp4 create mode 100644 _log/_site/bumblebee/poster.png create mode 100644 _log/_site/bumblebee/thumb_sm.png create mode 100644 _log/_site/e-reader.html create mode 100644 _log/_site/e-reader/circuit.svg create mode 100644 _log/_site/e-reader/ereader.mp4 create mode 100644 _log/_site/e-reader/poster.png create mode 100644 _log/_site/e-reader/source.tar.gz create mode 100644 _log/_site/e-reader/thumb_sm.png create mode 100644 _log/_site/etlas.html create mode 100644 _log/_site/etlas/circuit.svg create mode 100644 _log/_site/etlas/dash.jpg create mode 100644 _log/_site/etlas/etlas_arch.png create mode 100644 _log/_site/etlas/pcb.jpg create mode 100644 _log/_site/etlas/schematic.svg create mode 100644 _log/_site/etlas/source.tar.gz create mode 100644 _log/_site/etlas/thumb_sm.jpg create mode 100644 _log/_site/feed.xml create mode 100644 _log/_site/fpm-door-lock.html create mode 100644 _log/_site/fpm-door-lock/breadboard.jpg create mode 100644 _log/_site/fpm-door-lock/footprint.png create mode 100644 _log/_site/fpm-door-lock/gerber.zip create mode 100644 _log/_site/fpm-door-lock/pcb.jpg create mode 100644 _log/_site/fpm-door-lock/pcb1.jpg create mode 100644 _log/_site/fpm-door-lock/source.tar.gz create mode 100644 _log/_site/fpm-door-lock/thumb_sm.jpg create mode 100644 _log/_site/fpm-door-lock/video.mp4 create mode 100644 _log/_site/matrix-digital-rain.html create mode 100644 _log/_site/matrix-digital-rain/katakana.png create mode 100644 _log/_site/matrix-digital-rain/matrix.mp4 create mode 100644 _log/_site/matrix-digital-rain/poster.png create mode 100644 _log/_site/matrix-digital-rain/source.tar.gz create mode 100644 _log/_site/matrix-digital-rain/thumb_sm.png create mode 100644 _log/_site/mosfet-switches.html create mode 100644 _log/_site/mosfet-switches/bjt.png create mode 100644 _log/_site/mosfet-switches/n_high_side.png create mode 100644 _log/_site/mosfet-switches/p_high_side.png create mode 100644 _log/_site/my-first-pcb.html create mode 100644 _log/_site/my-first-pcb/back.jpeg create mode 100644 _log/_site/my-first-pcb/back_design.jpeg create mode 100644 _log/_site/my-first-pcb/front.jpeg create mode 100644 _log/_site/my-first-pcb/front_design.jpeg create mode 100644 _log/_site/my-first-pcb/gerber_back.zip create mode 100644 _log/_site/my-first-pcb/gerber_front.zip create mode 100644 _log/_site/my-first-pcb/source.tar.gz create mode 100644 _log/_site/my-first-pcb/thumb_sm.jpeg create mode 100644 _log/_site/neo4j-a-star-search.html create mode 100644 _log/_site/robots.txt create mode 100644 _log/_site/sitemap.xml create mode 100644 _log/_site/suckless-software.html create mode 100644 _log/neo4j-a-star-search.md (limited to '_log') diff --git a/_log/_site/arduino-due.html b/_log/_site/arduino-due.html new file mode 100644 index 0000000..172ee1a --- /dev/null +++ b/_log/_site/arduino-due.html @@ -0,0 +1,109 @@ +

This article is a step-by-step guide for programming bare-metal ATSAM3X8E chips +found on Arduino Due boards. It also includes notes on the chip’s memory layout +relevant for writing linker scripts. The steps described in this article were +tested on an OpenBSD workstation.

+ +

Toolchain

+ +

To interact directly with a bare-metal ATSAM3X8E chips, we must bypass the +embedded bootloader. To do that, we need a hardware programmer capable of +communicating with the chip over the Serial Wire Debug (SWD) protocol. Since +the workstation we upload the program from presumably doesn’t speak SWD, the +hardware programmer acts as a SWD-USB adapter. The ST-LINK/V2 programmer fits this +bill.

+ +

The OpenOCD on-chip debugger software supports +ATSAM3X8E chips. OpenOCD, on startup, runs a telnet server that we can connect to +to issue commands to the ATSAM3X8E chip. OpenOCD translates plain-text commands +into the binary sequences the chip understands, and sends them over the wire.

+ +

Finally, we need the ARM GNU Compiler +Toolchain to compile C programs for the chip. The ARM GNU compiler +toolchain and OpenOCD, as a consequence of being free software, are available +on every conceivable platform, including OpenBSD.

+ +

Electrical connections

+ +

The following photos illustrate the electrical connections between the Arduino +Due, PC, and the ST-LINK/V2 programmer required to transfer a compiled program +from a PC to the MCU.

+ + + + + + +
+ Pinout +

Wiring

+ 		+ Circuit +

Arduino Due

+
+ +

Arduino Due exposes the ATSAM3X8E’s SWD interface via its DEBUG port. The +ST-LINK/v2 programmer connects to that to communicate with the chip.

+ +

Uploading the program

+ +

The source.tar.gz tarball at the end of this page contains a sample C program +(the classic LED blink program) with OpenOCD configuration and linker scripts. +First, use the following command to build it:

+ +
$ arm-none-eabi-gcc -mcpu=cortex-m3 -mthumb -T script.ld \
+    -nostartfiles \
+    -nostdlib \
+    -o a.elf main.c
+
+ +

Then, open a telnet session with OpenOCD and issue the following sequence of +commands to configure the chip and upload the compiled program to it:

+ +
$ openocd -f openocd-due.cfg
+$ telnet localhost 4444
+  > halt
+  > at91sam3 gpnvm show
+  > at91sam3 gpnvm set 1
+  > at91sam3 gpnvm show
+$ openocd -f openocd-due.cfg -c "program a.elf verify reset exit"
+
+ +

The first of the above commands starts OpenOCD. In the telnet session, the +first command halts the chip in preparation for receiving commands. Next, we +inspect the current GPNVM bit setting (more on this later). If the bit is unset +(the gpnvm show command returns 0), we set it to 1 and verify the update.

+ +

The final command, issued from outside the telnet session, uploads the program +to the chip. Those are the bare minimum set of commands required to program the +chip. The AT91SAM3 flash driver section of the OpenOCD manual lists all +available commands for the ATSAM3X8E chip.

+ +

GPNVM bits

+ +

By design, ARM chips boot into address 0x00000. ATSAM3X8E’s memory consists of +a ROM and a dual-banked flash (flash0 and flash1), residing in different +locations of the chip’s address space. The GPNVM bits control which of them +maps to 0x00000. When GPNVM1 is cleared (the default), the chip boots from the ROM, +which contains Atmel’s SAM-BA bootloader.

+ +

Conversely, when the GPNVM1 bit is 1 (and the GPNVM2 bit is 0), flash0 at +address 0x80000 maps to 0x00000. When both GPNVM bits are 0, flash1 maps to +0x00000. Since we place our program in flash0 in the linker script, we set the +GPNVM1 bit and leave the GPNVM2 bit unchanged to ensure the chip +executes our program instead of the embedded bootloader at startup.

+ +

Linker script

+ +

At a minimum, the linker script must place the vector table at the first +address of the flash. This is mandatory for ARM chips unless we relocate the +vector table using the VTOR register.

+ +

The first entry of the vector table must be the stack pointer. The stack +pointer must be initialized to the highest memory location available to +accommodate the ATSAM3X8E’s descending stack.

+ +

The second entry of the vector table must be the reset vector. In the reset +vector, we can perform tasks such as zeroing out memory and initializing +registers before passing control to the main program.

+ +

Files: source.tar.gz

diff --git a/_log/_site/arduino-due/connections.jpeg b/_log/_site/arduino-due/connections.jpeg new file mode 100644 index 0000000..081e6d4 Binary files /dev/null and b/_log/_site/arduino-due/connections.jpeg differ diff --git a/_log/_site/arduino-due/schematic.png b/_log/_site/arduino-due/schematic.png new file mode 100644 index 0000000..62ddadd Binary files /dev/null and b/_log/_site/arduino-due/schematic.png differ diff --git a/_log/_site/arduino-due/source.tar.gz b/_log/_site/arduino-due/source.tar.gz new file mode 100644 index 0000000..496567b Binary files /dev/null and b/_log/_site/arduino-due/source.tar.gz differ diff --git a/_log/_site/arduino-uno.html b/_log/_site/arduino-uno.html new file mode 100644 index 0000000..d8ffac4 --- /dev/null +++ b/_log/_site/arduino-uno.html @@ -0,0 +1,76 @@ +

This is a quick reference for wiring up ATmega328P ICs to run at 5V and 3.3V. +While the 5V configuration is common, the 3.3V configuration can be useful in +low-power applications and when interfacing with parts that themselves run at +3.3V. In this guide, the 5V setup is configured with a 16MHz crystal +oscillator, while the 3.3V configuration makes use of an 8MHz crystal +oscillator.

+ +

The steps that follow refer to the following pinout.

+ + + + + + +
+ Pinout +

Pinout

+ 		+ Circuit +

Breadboard

+
+ +

5V-16MHz configuration

+ +

Powering ATmega328P microcontrollers with 5V is the most common setup. This is +also how Arduino Uno boards are wired.

+ +

In this configuration, the microcontroller’s pin 1 is connected to 5V via a +10kΩ resistor. Pins 9 and 10 are connected to a 16MHz crystal oscillator via +two 22pF capacitors connected to ground. The microcontroller is powered by +connecting pins 7, 20, and 21 to a 5V DC power supply. Lastly, pins 8 and 22 +are connected to ground. In addition to the these connections, which are +required, it’s a good idea to add 0.1μF decoupling capacitors between pins 7, +20, and 21 and ground.

+ +

Here’s a sample Makefile for compiling C programs for ATmega328P +microcontrollers using avr-gcc/avrdude toolchain.

+ +

3.3V-8MHz configuration

+ +

Electrical connections for running an ATmega328P at 3.3V are identical to that +of the 5V circuit. The only differences are that all the 5V connections are +replaced with a 3.3V power source and a 8MHz crystal oscillator takes the place +of the 16MHz crystal.

+ +

However, standard ATmega328P chips are preconfigured to run at 5V. To run one +at 3.3V, we must first modify its fuses that control characteristics like the +BOD level. If a bootloader that expects a 16MHz clock (e.g., Arduino +bootloader) is pre-installed on the ATmega328P, it must be swapped with one +that accepts an 8MHz clock. To accomplish that, we need an in-system programmer +(ISP).

+ +

Fortunately, we can turn an ordinary Arduino Uno board into an ISP by uploading +the ‘ArduinoISP’ sketch found in the Arduino IDE. The ISP communicates with the +microcontroller using a Serial Peripheral Interface (SPI). So, connect the SPI +port of the ATmega328P to that of the Arduino Uno, and the Uno’s SS pin +to the ATmega328P’s RESET pin.

+ +

Power up the the ATmega328P by connecting its VCC to a 5V supply (we +can use Arduino Uno’s 5V pin). From the Arduino IDE, select ‘ATmega328P (3.3V, +8MHz)’ for processor from the tools menu. Also from the tools menu, select +‘Arduino as ISP’ as programmer. Finally, upload the new bootloader by selecting +‘Burn Bootloader’ from the tools menu.

+ +

The ATmega328P is now ready to run at 8MHz with a 3.3V power supply. You can +upload programs to the ATmega328P as you normally would using avrdude. +Here’s a sample Makefile with adjusted parameters (e.g., baud +rate) for an 8MHz clock.

+ +

Remarks

+ +

In both configurations, if you intend to use the ATmega328P’s analog-to-digital +converter with the internal 1.1V or AVcc voltage as reference, do +not connect AREF (pin 21) to Vcc. Refer to section 23.5.2 in the +datasheet for more information.

+ diff --git a/_log/_site/arduino-uno/3v3.Makefile b/_log/_site/arduino-uno/3v3.Makefile new file mode 100644 index 0000000..4ca89d4 --- /dev/null +++ b/_log/_site/arduino-uno/3v3.Makefile @@ -0,0 +1,46 @@ +CC = avr-gcc +MCU = atmega328p +PORT = /dev/cuaU0 +TARGET = app + +SRC = main.c +OBJ = $(SRC:.c=.o) + +CFLAGS = -std=gnu99 +CFLAGS += -Os +CFLAGS += -Wall +CFLAGS += -mmcu=$(MCU) +CFLAGS += -DBAUD=57600 +CFLAGS += -DF_CPU=8000000UL +CFLAGS += -ffunction-sections -fdata-sections + +LDFLAGS = -mmcu=$(MCU) +LDFLAGS += -Wl,--gc-sections + +HEX_FLAGS = -O ihex +HEX_FLAGS += -j .text -j .data + +AVRDUDE_FLAGS = -p $(MCU) +AVRDUDE_FLAGS += -c arduino +AVRDUDE_FLAGS += -b 57600 +AVRDUDE_FLAGS += -P $(PORT) +AVRDUDE_FLAGS += -D -U + +%.o: %.c + $(CC) $(CFLAGS) -c -o $@ $< + +elf: $(OBJ) + $(CC) $(LDFLAGS) $(OBJ) -o $(TARGET).elf + +hex: elf + avr-objcopy $(HEX_FLAGS) $(TARGET).elf $(TARGET).hex + +upload: hex + avrdude $(AVRDUDE_FLAGS) flash:w:$(TARGET).hex:i + +.PHONY: clean + +clean: + rm -f *.o *.elf *.hex + + diff --git a/_log/_site/arduino-uno/Makefile b/_log/_site/arduino-uno/Makefile new file mode 100644 index 0000000..9db7b09 --- /dev/null +++ b/_log/_site/arduino-uno/Makefile @@ -0,0 +1,43 @@ +CC = avr-gcc +MCU = atmega328p +PORT = /dev/cuaU0 +TARGET = app + +SRC = main.c +OBJ = $(SRC:.c=.o) + +CFLAGS = -std=gnu99 +CFLAGS += -Os +CFLAGS += -Wall +CFLAGS += -mmcu=$(MCU) +CFLAGS += -DBAUD=115200 +CFLAGS += -DF_CPU=16000000UL +CFLAGS += -ffunction-sections -fdata-sections + +LDFLAGS = -mmcu=$(MCU) +LDFLAGS += -Wl,--gc-sections + +HEX_FLAGS = -O ihex +HEX_FLAGS += -j .text -j .data + +AVRDUDE_FLAGS = -p $(MCU) +AVRDUDE_FLAGS += -c arduino +AVRDUDE_FLAGS += -P $(PORT) +AVRDUDE_FLAGS += -D -U + +%.o: %.c + $(CC) $(CFLAGS) -c -o $@ $< + +elf: $(OBJ) + $(CC) $(LDFLAGS) $(OBJ) -o $(TARGET).elf + +hex: elf + avr-objcopy $(HEX_FLAGS) $(TARGET).elf $(TARGET).hex + +upload: hex + avrdude $(AVRDUDE_FLAGS) flash:w:$(TARGET).hex:i + +.PHONY: clean + +clean: + rm *.o *.elf *.hex diff --git a/_log/_site/arduino-uno/breadboard.jpeg b/_log/_site/arduino-uno/breadboard.jpeg new file mode 100644 index 0000000..bd74907 Binary files /dev/null and b/_log/_site/arduino-uno/breadboard.jpeg differ diff --git a/_log/_site/arduino-uno/pinout.png b/_log/_site/arduino-uno/pinout.png new file mode 100644 index 0000000..59acfbc Binary files /dev/null and b/_log/_site/arduino-uno/pinout.png differ diff --git a/_log/_site/bumblebee.html b/_log/_site/bumblebee.html new file mode 100644 index 0000000..a466d0b --- /dev/null +++ b/_log/_site/bumblebee.html @@ -0,0 +1,40 @@ +

Bumblebee is a tool I built for one of my employers to automate the generation +of web scraping scripts.

+ + + +

In 2024, we were tasked with collecting market data using various methods, +including scraping data from authorized websites for traders’ use.

+ +

Manual authoring of such scripts took time. The scripts were often brittle due +to the complexity of the modern web, and they lacked optimizations such as +bypassing the UI and retrieving the data files directly when possible, which +would have significantly reduced our compute costs.

+ +

To alleviate these challenges, I, with the help of a colleague, Andy Zhang, +built Bumblebee: a web browser powered by C# Windows Forms, Microsoft Edge WebView2, and +the Scintilla.NET text editor.

+ +

Bumblebee works by injecting a custom JavaScript program that intercepts +client-side events and sends them to Bumblebee for analysis. In addition to +front-end events, Bumblebee also captures internal browser events, which it +then interprets to generate code in real time. Note that we developed Bumblebee +before the advent of now-popular LLMs. Bumblebee supports dynamic websites, +pop-ups, developer tools, live manual override, event debouncing, and filtering +hidden elements and scripts.

+ +

Before settling on a desktop application, we contemplated designing Bumblebee +as a browser extension. We chose the desktop app because extensions don’t offer +the deep, event-based control we needed. Besides, the company’s security +policy, which prohibited browser extensions, would have complicated the +deployment of an extension-based solution. My first prototype used a C# binding +of the Chromium project. WebView’s more intuitive API and its seamless +integration with Windows Forms led us to choose it over the Chromium wrapper.

+ +

What began as a personal side project to improve my own workflow enabled us to +collectively improve the quality of our web scripts at a much larger scale. +Bumblebee predictably reduced the time we spent on authoring scripts from hours +to a few minutes.

+ diff --git a/_log/_site/bumblebee/bee.mp4 b/_log/_site/bumblebee/bee.mp4 new file mode 100644 index 0000000..835600d Binary files /dev/null and b/_log/_site/bumblebee/bee.mp4 differ diff --git a/_log/_site/bumblebee/poster.png b/_log/_site/bumblebee/poster.png new file mode 100644 index 0000000..6dc955e Binary files /dev/null and b/_log/_site/bumblebee/poster.png differ diff --git a/_log/_site/bumblebee/thumb_sm.png b/_log/_site/bumblebee/thumb_sm.png new file mode 100644 index 0000000..f7cfbf3 Binary files /dev/null and b/_log/_site/bumblebee/thumb_sm.png differ diff --git a/_log/_site/e-reader.html b/_log/_site/e-reader.html new file mode 100644 index 0000000..f60c485 --- /dev/null +++ b/_log/_site/e-reader.html @@ -0,0 +1,85 @@ +

This project features an experimental e-reader powered by an ESP-WROOM-32 +development board and a 7.5-inch Waveshare +e-paper display built with the intention of learning about e-paper displays.

+ + + +

Introduction

+ +

The prototype e-reader comprises an ESP32 microcontroller, an e-paper display +HAT, and three buttons: yellow, blue, and white for turning the page backwards, +forwards, and putting the device to sleep, respectively. The prototype does not +store books on the microcontroller. It streams books from a server over HTTP. +The e-reader employs RTC memory to record the reading progress between +sessions.

+ +

The most formidable challenge when trying to build an e-reader with an ESP32 is +its limited memory and storage. My ESP-WROOM-32 has a total of 512KB of SRAM +and 4MB of flash memory, which the freeRTOS, ESP-IDF, and the e-reader +application must share. To put things into perspective, a Kindle Paperwhite has +at least 256MB of memory and 8GB of storage. That is 500x more memory than what +I’d have to work with.

+ +

Despite its size, as microcontrollers go, ESP32 is a powerful system-on-a-chip +with a 160MHz dual-core processor and integrated WiFi. So, I thought it’d be +amusing to embrace the constraints and build my e-reader using a $5 MCU and the +power of C programming.

+ +

The file format

+ +

The file format dictates the complexity of the embedded software. So, I’ll +begin there. The e-reader works by downloading and rendering a rasterized +monochrome image of a page (a .ebm file).

+ +

The EBM file contains a series of bitmaps, one for each page of the book. The +dimensions of each bitmap are equal to the size of the display. Each byte of +the bitmap encodes information for rendering eight pixels. For my display, +which has a resolution of 480x800, the bitmaps are laid out along 48KB +boundaries. This simple file format lends well to HTTP streaming, which is its +main advantage, as we will soon see.

+ +

The pdftoebm.py script enclosed in the tarball at the end of the page converts +PDF documents to EBM files.

+ +

How does it work?

+ +

As the e-reader has no storage, it can’t store books locally. Instead, it +downloads pages of the EBM file over HTTP from the location pointed to by the +EBM_ARCH_URL setting in the Kconfig.projbuild file on demand. To read a +different book, we have to replace the old file with the new one or change the +EBM_ARCH_URL value. The latter requires us to recompile the embedded +software.

+ +

Upon powering up, the e-reader checks the reading progress stored in the RTC +memory. It then downloads three pages (current, previous, and next) to a +circular buffer in DMA-capable memory. When the user turns a page by pressing a +button, one of the microprocessor’s two cores transfers it from the buffer to +the display over a Serial Peripheral Interface (SPI). The other downloads a new +page in the background. I used the ESP-IDF task API to schedule the two tasks +on different cores of the multicore processor to make the reader more +responsive.

+ +

I designed the EBM format with HTTP streaming in mind. Since the pages are laid +out in the EBM file along predictable boundaries, the e-reader can request +pages by specifying the offset and the chunk size in the HTTP Range header. Any +web server will process this request without custom logic.

+ +

Epilogue

+ +

My fascination with e-paper began back in 2017, when I was tasked with +installing a few displays in a car park. Having no idea how they worked, I +remember watching the languid screens refresh like a Muggle witnessing magic. +This project was born out of that enduring curiosity and love of e-paper +technology.

+ +

Why did I go to the trouble of building a rudimentary e-reader when I could +easily buy a more capable commercial e-reader? First of all, it’s to prove to +myself that I can. More importantly, there’s a quiet satisfaction to reading on +hardware you built yourself. You are no longer the powerless observer watching +the magic happen from the sidelines. You become the wizard who makes the +invisible particles swirl into form by whispering C to them. There’s only one +way to experience that.

+ +

Files: source.tar.gz

diff --git a/_log/_site/e-reader/circuit.svg b/_log/_site/e-reader/circuit.svg new file mode 100644 index 0000000..fd7508b --- /dev/null +++ b/_log/_site/e-reader/circuit.svg @@ -0,0 +1,145 @@ + + + + + + + + + + + 10 kΩ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 1 + 2 + 3 + 4 + + + + + + + + + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + + + + + 5 + 6 + 7 + 8 + BUS + E-Paper Display HAT + + + CS + + DC + + DIN + + CLK + + BUSY + + RST + + GND + + VCC + + ESP-WROOM-32 + + IO21 + + + IO5 + + + IO16 + + + IO23 + + + IO18 + + + IO22 + + + IO4 + + + IO2 + + + GND + + + 3V3 + + + GND + + + IO15 + + + + \ No newline at end of file diff --git a/_log/_site/e-reader/ereader.mp4 b/_log/_site/e-reader/ereader.mp4 new file mode 100644 index 0000000..89e05eb Binary files /dev/null and b/_log/_site/e-reader/ereader.mp4 differ diff --git a/_log/_site/e-reader/poster.png b/_log/_site/e-reader/poster.png new file mode 100644 index 0000000..1e222d2 Binary files /dev/null and b/_log/_site/e-reader/poster.png differ diff --git a/_log/_site/e-reader/source.tar.gz b/_log/_site/e-reader/source.tar.gz new file mode 100644 index 0000000..3e343a7 Binary files /dev/null and b/_log/_site/e-reader/source.tar.gz differ diff --git a/_log/_site/e-reader/thumb_sm.png b/_log/_site/e-reader/thumb_sm.png new file mode 100644 index 0000000..7c971e8 Binary files /dev/null and b/_log/_site/e-reader/thumb_sm.png differ diff --git a/_log/_site/etlas.html b/_log/_site/etlas.html new file mode 100644 index 0000000..06e3ce7 --- /dev/null +++ b/_log/_site/etlas.html @@ -0,0 +1,103 @@ +

Etlas is a news, stock market, and weather tracker powered by an ESP32 NodeMCU +D1, featuring a 7.5-inch Waveshare e-paper display and a +DHT22 sensor module.

+ + + + + + +
frontback
+ +

The top-left panel shows two weeks of end-of-day prices—the maximum the ESP32’s +SRAM can hold—from the Polygon.io API. The price feed is relayed through a +FastCGI-wrapped Flask app hosted on a VPS. This lets me configure stock symbols +in its application settings. The app cycles through them as requests come in +from the ESP32. Running the Flask app as a FastCGI process while exposing it +via httpd with htpasswd authentication keeps the server code simple and secure.

+ +

The following diagram outlines the Etlas’s overall system architecture.

+ +

architecture

+ +

The more prominent panel on the right of the display shows local and world news +from Channel NewsAsia. The MCU downloads and parses XML data from the RSS feed +directly before rendering it to the display. The character glyphs used are +stored as bitmaps in the sprites directory. I skipped the proxy for news to +avoid writing more server code, but in hindsight it limits the feeds Etlas can +handle. I will fix this in a future version.

+ +

The middle and bottom right panels display the temperature and relative +humidity from the DHT22 sensor. The DHT22 uses pulse-width modulation to +transmit data to the host. The 26µs, 50µs, and 70µs pulses are too fast for the +ESP32 to measure reliably with standard APIs. Instead, the driver compares +relative pulse widths to differentiate zeros from ones:

+ +
static inline int dht_await_pin_state(int state, int timeout)
+{
+    int t;
+    static const uint16_t delta = 1;
+
+    for (t = 0; t < timeout; t += delta) {
+        ets_delay_us(delta);
+        if (gpio_get_level(DHT_PIN) == state)
+          return t;
+    }
+    return 0;
+}
+
+static inline int dht_get_raw_data(unsigned char buf[DHT_DATA_LEN])
+{
+    int rc;
+    unsigned char i, pwl, pwh;
+
+    gpio_set_level(DHT_PIN, 0);
+    ets_delay_us(1100);
+    gpio_set_level(DHT_PIN, 1);
+
+    if (!dht_await_pin_state(0, 40)) {
+        rc = 1;
+        xQueueSend(dht_evt_queue, &rc, (TickType_t) 0);
+        return 0;
+    }
+    if (!dht_await_pin_state(1, 80)) {
+        rc = 2;
+        xQueueSend(dht_evt_queue, &rc, (TickType_t) 0);
+        return 0;
+    }
+    if (!dht_await_pin_state(0, 80)) {
+        rc = 3;
+        xQueueSend(dht_evt_queue, &rc, (TickType_t) 0);
+        return 0;
+    }
+
+    for (i = 0; i < DHT_DATA_LEN; i++) {
+        if (!(pwl = dht_await_pin_state(1, 50))) {
+            rc = 4;
+            xQueueSend(dht_evt_queue, &rc, (TickType_t) 0);
+            return 0;
+        }
+        if (!(pwh = dht_await_pin_state(0, 70))) {
+            rc = 5;
+            xQueueSend(dht_evt_queue, &rc, (TickType_t) 0);
+            return 0;
+        }
+        buf[i] = pwh > pwl;
+    }
+    return 1;
+}
+
+ +

I ported this implementation from ESP8266 +to ESP32—all credit for the algorithm belongs to them.

+ +

Etlas is a networked embedded system. All acquisition, processing, and +rendering of data are performed on the ESP32’s 160MHz microprocessor using less +than 512KB of SRAM. The embedded software that makes this possible is written +in C using ESP-IDF v5.2.1. The e-paper display driver is derived from Waveshare +examples for Arduino and STM32 +platforms.

+ +

Etlas has been running reliably for over a year since August 2024.

+ +

Files: source.tar.gz

diff --git a/_log/_site/etlas/circuit.svg b/_log/_site/etlas/circuit.svg new file mode 100644 index 0000000..6255045 --- /dev/null +++ b/_log/_site/etlas/circuit.svg @@ -0,0 +1,105 @@ + + + + + + + + + + + + + + + + AM2302 + + + DATA + + GND + + VCC + E-Paper display HAT + + + CS + + DC + + DIN + + CLK + + BUSY + + RST + + PWR + + GND + + VCC + + + + + + + + + + + + + + 1 + 2 + 3 + 4 + + + + + 1 + 2 + 3 + 4 + + ESP32 Mini NodeMCU D1 + + IO19 + + + IO15 + + + GND + + + IO27 + + + IO14 + + + IO13 + + + IO25 + + + IO26 + + + IO16 + + + GND + + + 3V3 + + + \ No newline at end of file diff --git a/_log/_site/etlas/dash.jpg b/_log/_site/etlas/dash.jpg new file mode 100644 index 0000000..cf4efc6 Binary files /dev/null and b/_log/_site/etlas/dash.jpg differ diff --git a/_log/_site/etlas/etlas_arch.png b/_log/_site/etlas/etlas_arch.png new file mode 100644 index 0000000..241e9f1 Binary files /dev/null and b/_log/_site/etlas/etlas_arch.png differ diff --git a/_log/_site/etlas/pcb.jpg b/_log/_site/etlas/pcb.jpg new file mode 100644 index 0000000..fcb40fa Binary files /dev/null and b/_log/_site/etlas/pcb.jpg differ diff --git a/_log/_site/etlas/schematic.svg b/_log/_site/etlas/schematic.svg new file mode 100644 index 0000000..3070dd1 --- /dev/null +++ b/_log/_site/etlas/schematic.svg @@ -0,0 +1,4 @@ + + + +152726131425193V3GND
ESP32 Mini NodeMCU D1
ESP32 Mini NodeMCU D1
DHT22
DHT22
E-paper HAT
E-paper HAT
3.3V
3.3V
3.3V
3.3V
3.3V
3.3V
CS
CS
DC
DC
RST
RST
CLK
CLK
MOSY
MOSY
BUSY
BUSY
VCC
VCC
GND
GND
VCC
VCC
GND
GND
DATA
DATAText is not SVG - cannot display \ No newline at end of file diff --git a/_log/_site/etlas/source.tar.gz b/_log/_site/etlas/source.tar.gz new file mode 100644 index 0000000..8b12cf6 Binary files /dev/null and b/_log/_site/etlas/source.tar.gz differ diff --git a/_log/_site/etlas/thumb_sm.jpg b/_log/_site/etlas/thumb_sm.jpg new file mode 100644 index 0000000..a374879 Binary files /dev/null and b/_log/_site/etlas/thumb_sm.jpg differ diff --git a/_log/_site/feed.xml b/_log/_site/feed.xml new file mode 100644 index 0000000..ab90c82 --- /dev/null +++ b/_log/_site/feed.xml @@ -0,0 +1 @@ +Jekyll2025-12-24T08:01:11+08:00/feed.xml \ No newline at end of file diff --git a/_log/_site/fpm-door-lock.html b/_log/_site/fpm-door-lock.html new file mode 100644 index 0000000..820af3f --- /dev/null +++ b/_log/_site/fpm-door-lock.html @@ -0,0 +1,105 @@ +

This project features a fingerprint door lock powered by an ATmega328P +microcontroller.

+ + + +

Overview

+ +

The lock comprises three subsystems: the ATmega328P microcontroller, an R503 +fingerprint sensor, and an FS5106B high-torque servo. The sensor mounted on the +front surface of the door enables users to unlock it from the outside. The +servo is attached to the interior door knob. The MCU must be installed at the +back of the door to prevent unauthorized users from tampering with it.

+ +

When no one is interacting with the lock, the MCU is in deep sleep. The sensor +and the servo each draw 13.8mA and 4.6mA of quiescent currents. To prevent this +idle current draw, the MCU employs MOSFETs to cut off power to them before +entering deep sleep. Doing so is crucial for conserving the battery.

+ +

Without power, the sensor remains in a low-power state, drawing approximately +2.9μA through a separate power rail. When a finger comes into contact with the +sensor, the sensor triggers a pin change interrupt, waking up the MCU. The MCU +activates a MOSFET, which in turn activates the sensor. Over UART, the MCU +unlocks the sensor and issues commands to scan and match the fingerprint.

+ +

If the fingerprint matches an enrolled fingerprint, the MCU activates the blue +LED on the sensor, turns on the MOSFET connected to the servo, and sends a PWM +signal to the servo to unlock the door. Otherwise, the MCU activates the red +LED on the sensor. Finally, the MCU deactivates the MOSFETS and goes back to +sleep.

+ +

Embedded software

+ +

The embedded software, written in C, includes a driver for the sensor, servo +control routines, and a battery monitoring system.

+ +

In addition to controlling the sensor and the servo, the program strives to +maintain precise control over the microcontroller’s sleep modes, as well as +when the peripherals are activated and for how long they remain active. I +thoroughly enjoyed writing the embedded software. There’s something magical +about being able to alter the physical world around you by uttering a few lines +of C code.

+ +

The source code of the project, which includes a driver for the R503 +fingerprint sensor module, is enclosed in the tarball linked at the end of the +page.

+ +

The PCB

+ +

For this project, I designed a custom PCB and had it fabricated by JLCPCB. Like +the software, the circuit is primarily concerned with optimizing power +consumption and extending battery life.

+ + + + + + + + + +
+ PCB + + Design +
+ PCB footprint +
+ +

Consequently, the principal components of the circuit are the 2N7000 and +NDP6020P field-effect transistors. They switch power electronically to the +servo and the fingerprint sensor, the two most power-hungry parts of the +circuit. The two MP1584EN buck converters play an axial role in efficiently +regulating power to the MCU and the sensor.

+ +

The ATmega328P typically operates at 5V with a 16MHz crystal oscillator. To +further reduce power consumption, I modified the ATmega328P’s fuses to run at +3.3V with an 8MHz crystal oscillator.

+ +

The bottom right area of the PCB isolates the power supply of the servo from +the rest of the circuit. This shields components such as the MCU from the +servo’s high current draw, which can exceed 1A. The IN4007 diode in slot U2 +serves as a flyback diode, protecting the MOSFET from reverse currents +generated by the servo.

+ +

Lastly, the 56kΩ and 10kΩ resistors in slots R10 and R11 form a voltage divider +circuit. Its output is fed to the ADC of the MCU, which measures the supply +voltage by comparing it to the internal bandgap reference voltage.

+ +

Epilogue

+ +

This project began nearly a year ago when I attempted to unlock our door +wirelessly by writing to the UART ports of two MCUs connected to inexpensive +433MHz RF transceivers. Although I failed, it led me down a rabbit hole of RF +communications, MOSFETs, PCB design, and low-power circuits.

+ +

During the project, I reinvented the wheel many times. I implemented a +low-level network stack using only RF modules and an 8-bit microcontroller, +designed my first PCB, and developed drivers from scratch. The project was far +from a smooth sail. Bad electrical connections, soldering and desoldering, and +the heartache of purchasing the wrong parts were routine. It was a long but +rewarding journey from the messy breadboard to the shiny PCB.

+ +

Files: source.tar.gz, gerber.zip

diff --git a/_log/_site/fpm-door-lock/breadboard.jpg b/_log/_site/fpm-door-lock/breadboard.jpg new file mode 100644 index 0000000..2bf47a9 Binary files /dev/null and b/_log/_site/fpm-door-lock/breadboard.jpg differ diff --git a/_log/_site/fpm-door-lock/footprint.png b/_log/_site/fpm-door-lock/footprint.png new file mode 100644 index 0000000..5511bf1 Binary files /dev/null and b/_log/_site/fpm-door-lock/footprint.png differ diff --git a/_log/_site/fpm-door-lock/gerber.zip b/_log/_site/fpm-door-lock/gerber.zip new file mode 100644 index 0000000..19a9d19 Binary files /dev/null and b/_log/_site/fpm-door-lock/gerber.zip differ diff --git a/_log/_site/fpm-door-lock/pcb.jpg b/_log/_site/fpm-door-lock/pcb.jpg new file mode 100644 index 0000000..fbd800b Binary files /dev/null and b/_log/_site/fpm-door-lock/pcb.jpg differ diff --git a/_log/_site/fpm-door-lock/pcb1.jpg b/_log/_site/fpm-door-lock/pcb1.jpg new file mode 100644 index 0000000..367187d Binary files /dev/null and b/_log/_site/fpm-door-lock/pcb1.jpg differ diff --git a/_log/_site/fpm-door-lock/source.tar.gz b/_log/_site/fpm-door-lock/source.tar.gz new file mode 100644 index 0000000..ef23422 Binary files /dev/null and b/_log/_site/fpm-door-lock/source.tar.gz differ diff --git a/_log/_site/fpm-door-lock/thumb_sm.jpg b/_log/_site/fpm-door-lock/thumb_sm.jpg new file mode 100644 index 0000000..a8fa534 Binary files /dev/null and b/_log/_site/fpm-door-lock/thumb_sm.jpg differ diff --git a/_log/_site/fpm-door-lock/video.mp4 b/_log/_site/fpm-door-lock/video.mp4 new file mode 100644 index 0000000..a907a9b Binary files /dev/null and b/_log/_site/fpm-door-lock/video.mp4 differ diff --git a/_log/_site/matrix-digital-rain.html b/_log/_site/matrix-digital-rain.html new file mode 100644 index 0000000..85bac5d --- /dev/null +++ b/_log/_site/matrix-digital-rain.html @@ -0,0 +1,103 @@ +

The Matrix digital rain implemented in raw C using ANSI escape sequences with +zero dependencies—not even ncurses.

+ + + +

This project began over three years ago as a fork of Domsson’s unique rendition +of the Matrix rain: Fakesteak. I +aimed to modify the algorithm to produce a rain that resembled the original +with high visual fidelity.

+ +

Unicode support

+ +

Unicode support in the 2022 version lacked flexibility. The charset used in the +rain had to be a single contiguous block defined by UNICODE_MIN and +UNICODE_MAX settings:

+ +
#define UNICODE_MIN 0x0021
+#define UNICODE_MAX 0x007E
+
+static inline void insert_code(matrix *mat,
+    size_t row, size_t col) 
+{
+    mat->code[index(mat, row, col)] = rand()
+        % (UNICODE_MAX - UNICODE_MIN)
+        + UNICODE_MIN;
+}
+
+ +

There was no way, for instance, to use both ASCII and Katakana at the same +time. The user had to pick one. In the new version, the user can use any number +of Unicode blocks using glyphs array. In fact, the default rain now includes +both ASCII and half-width Katakana characters:

+ +
#define UNICODE(min, max)  (((uint64_t)max << 32) | min)
+
+static uint64_t glyphs[] = {
+    UNICODE(0x0021, 0x007E), /* ASCII */
+    UNICODE(0xFF65, 0xFF9F), /* Half-width Katakana */
+};
+
+static uint8_t glyphlen = (sizeof glyphs) / (sizeof glyphs[0]);
+
+static inline void insert_code(matrix *mat,
+    size_t row, size_t col) 
+{
+    uint64_t block;
+    uint32_t unicode_min, unicode_max;
+
+    block = glyphs[(rand() % glyphlen)];
+    unicode_min = (uint32_t)block;
+    unicode_max = (uint32_t)(block >> 32);
+
+    mat->code[index(mat, row, col)] = rand()
+        % (unicode_max - unicode_min)
+        + unicode_min;
+}
+
+ +

Entries in the glyphs array are Unicode blocks bit-packed in an 8-byte +container: the four low bytes forms the first codepoint and the four high bytes +the last.

+ +

Phosphor decay

+ +

The dim afterglow of monochrome CRT displays is achieved by carefully scaling +the RGB channels individually and mixing them:

+ +
#define DECAY_MPLIER  2
+
+static inline void blend(matrix *mat,
+    size_t row, size_t col)
+{
+    unsigned char *color;
+
+    color = mat->rgb[index(mat, row, col)].color;
+    color[R] = color[R] - (color[R] - RGB_BG_RED) / DECAY_MPLIER;
+    color[G] = color[G] - (color[G] - RGB_BG_GRN) / DECAY_MPLIER;
+    color[B] = color[B] - (color[B] - RGB_BG_BLU) / DECAY_MPLIER;
+}
+
+ +

The blending function emulates the phosphor decay by gradually transitioning +each raindrop’s color towards the background color. The multiplier is the +number of passes over the rain track needed before the afterglow disappears.

+ +

Nonetheless, the rain resembles the original with high visual fidelity. It’s +highly customizable and gentle on the CPU. On my 14” ThinkPad T490, which has a +resolution of 1920x1080 and 4GHz CPU, it uses 2-3% of the CPU with occasional +jumps of up to about 8%. Not too bad for a weekend project. The program has +been tested with xterm and urxvt terminal emulators on OpenBSD and Arch Linux +systems. Someone has managed to get it moving on a Raspberry Pi as well.

+ +

Lastly, to compile and run:

+ +
$ cc -O3 main.c -o matrix
+$ ./matrix
+
+ +

“All I see is blonde, brunette, red head.”

+ +

Files: source.tar.gz

diff --git a/_log/_site/matrix-digital-rain/katakana.png b/_log/_site/matrix-digital-rain/katakana.png new file mode 100644 index 0000000..b9df873 Binary files /dev/null and b/_log/_site/matrix-digital-rain/katakana.png differ diff --git a/_log/_site/matrix-digital-rain/matrix.mp4 b/_log/_site/matrix-digital-rain/matrix.mp4 new file mode 100644 index 0000000..7edf5d6 Binary files /dev/null and b/_log/_site/matrix-digital-rain/matrix.mp4 differ diff --git a/_log/_site/matrix-digital-rain/poster.png b/_log/_site/matrix-digital-rain/poster.png new file mode 100644 index 0000000..1f68ca4 Binary files /dev/null and b/_log/_site/matrix-digital-rain/poster.png differ diff --git a/_log/_site/matrix-digital-rain/source.tar.gz b/_log/_site/matrix-digital-rain/source.tar.gz new file mode 100644 index 0000000..5a69236 Binary files /dev/null and b/_log/_site/matrix-digital-rain/source.tar.gz differ diff --git a/_log/_site/matrix-digital-rain/thumb_sm.png b/_log/_site/matrix-digital-rain/thumb_sm.png new file mode 100644 index 0000000..940965a Binary files /dev/null and b/_log/_site/matrix-digital-rain/thumb_sm.png differ diff --git a/_log/_site/mosfet-switches.html b/_log/_site/mosfet-switches.html new file mode 100644 index 0000000..c1a7b52 --- /dev/null +++ b/_log/_site/mosfet-switches.html @@ -0,0 +1,110 @@ +

Recently, I needed a low-power circuit for one of my battery-operated projects. +Much of the system’s power savings depended on its ability to electronically +switch off components, such as servos, that draw high levels of quiescent +currents. My search for a solution led me to MOSFETs, transistors capable of +controlling circuits operating at voltages far above their own.

+ +

Acknowledgments

+ +

This article is a summary of what I learnt about using MOSFETs as switches. +I’m not an electronics engineer, and this is not an authoritative guide. The +circuits in this post must be considered within the narrow context in which +I’ve used them. All credits for the schematics belong to Simon Fitch.

+ +

Preamble

+ +

For a typical MOSFET-based switch, we can connect a GPIO pin of a +microcontroller to the gate of a logic-level N-channel MOSFET placed on the low +side of the load and tie the gate and the drain pins of the MOSFET with a +pull-down resistor. This would work as long as the power supplies of the +microcontroller and the load don’t share a common ground. Things become more +complicated when they do (e.g., controlling power to a component driven by the +same microcontroller).

+ +

In that scenario, the source potential visible to the load is the difference +between the gate and the threshold potentials of the MOSFET. For example, when +the gate and the threshold potentials are 3.3 V and 1.5 V, the potential the +load sees is 1.8 V. So, to use a low-side N-channel MOSFET, we need the gate +potential to be higher than the source potential, which may not always be +practical. The alternative would be a hide-side switch.

+ +

P-channel high-side switch

+ +

The following schematic shows how a high-side P-channel MOSFET (M1) could +switch power to a 6 V servo driven by a 3.3 V MCU.

+ +

P-channel high-side switching circuit

+ +

When the microcontroller outputs low, the M2 N-channel MOSFET stops conducting. +The R1 resistor pulls the gate of the M1 P-channel MOSFET up to +6 V, switching +the servo off. When the microcontroller outputs high on the GPIO pin, M2’s +source-drain connection starts conducting, causing M1’s gate potential to drop +to 0 V, which switches on power to the servo.

+ +

N-channel high-side switch

+ +

The P-channel high-side switch would be the typical architecture for our use +case. However, if we have access to a potential high enough to safely raise the +gate potential above the threshold such that their difference outputs the source +potential required to drive the load, we can switch on the high side using an +N-channel MOSFET:

+ +

N-channel high-side switching circuit

+ +

In the schematic, both M1 and M2 are N-channel MOSFETs. When the +microcontroller output is low, M2 stops conducting. This causes the M1’s gate +potential to rise above the threshold, turning the servo on. Conversely, a high +output on the GPIO line switches M2 on, which lowers M1’s gate potential. This +switches the servo off. The R2 pull-up resistor prevents the high impedance of +the output pins at power-up from switching the servo on.

+ +

Both topologies require M2 to act as a level converter between circuits +containing the microcontroller and the servo, converting between 0 V and +6 V +or +9 V. M2 is a low-power signal converter carrying less than a milliamp of +current. The gate-source threshold voltage of M2 must be lower than the MCU’s +supply voltage. 2N7000, 2N7002, and BSS138 are popular choices for M2.

+ +

The D1 flyback diodes used in the two topologies safeguard the MOSFET from +voltage spikes caused by inductive loads such as servos.

+ +

A BJT alternative

+ +

A Bipolar Junction Transistor (BJT) is a simpler, cheaper, and more widely +available type of transistor that can be used as a switch.

+ +

BJT architecture

+ +

In the schematic, when the MCU outputs high, Q2 starts conducting. Q2 amplifies +Q1’s base current. Unlike MOSFETs, which are voltage-driven, BJTs are driven by +base current. Resistors R3 and R4 must be chosen carefully to output the +desired base currents. “How to choose a +transistor as a switch” is an excellent guide on using BJTs as electronic +switches.

+ +

Which topology to choose?

+ +

The professional community appears to prefer MOSFETs over BJTs. MOSFETs are +more efficient when the switch is on. However, they are more challenging to +drive, especially with a 3.3 V MCU, due to the VGS potentials +required to achieve specified RDS(on) values (i.e., to turn them on +fully).

+ +

N-channel MOSFETs have lower on-resistance values, making them more efficient +than P-channel ones. They are also cheaper. However, they are harder to drive +on the high side as their gate potential must be higher than the source +potential. This often requires extra circuitry such as MOSFET drivers.

+ +

Further reading

+ + diff --git a/_log/_site/mosfet-switches/bjt.png b/_log/_site/mosfet-switches/bjt.png new file mode 100644 index 0000000..9858fa7 Binary files /dev/null and b/_log/_site/mosfet-switches/bjt.png differ diff --git a/_log/_site/mosfet-switches/n_high_side.png b/_log/_site/mosfet-switches/n_high_side.png new file mode 100644 index 0000000..c851768 Binary files /dev/null and b/_log/_site/mosfet-switches/n_high_side.png differ diff --git a/_log/_site/mosfet-switches/p_high_side.png b/_log/_site/mosfet-switches/p_high_side.png new file mode 100644 index 0000000..9f5397a Binary files /dev/null and b/_log/_site/mosfet-switches/p_high_side.png differ diff --git a/_log/_site/my-first-pcb.html b/_log/_site/my-first-pcb.html new file mode 100644 index 0000000..d5e886b --- /dev/null +++ b/_log/_site/my-first-pcb.html @@ -0,0 +1,57 @@ +

In 2023, I started tinkering with DIY electronics as a hobby. Until now, I’ve +been using development boards like the Arduino Uno and ESP-32-WROOM so that I +can focus on the software. Recently, I decided to step outside of my comfort +zone and design a PCB from scratch for a door lock I’m working on.

+ +

The lock comprises two subsystems: a fingerprint sensor in front of the door +and a servo connected to the physical lock behind the door. The fingerprint +sensor authenticates the person and signals the servo behind the door to unlock +the door over an encrypted RF channel.

+ + + + + + + + + + +
+ Design (front) +

Footprint (front)

+ 		+ PCB (front) +

PCB (front)

+
+ Design (back) +

Footprint (back)

+ 		+ PCB (back) +

PCB (back)

+
+ +

The PCBs have two layers. A copper region serves as the ground plane. The 0.3mm +wide 1oz/ft2 copper traces can carry up to 500mA (the tracks +connecting the power source and the linear regulators have a width of 0.5mm). +Both subsystems were functional. I was able to control the servo reliably using +the fingerprint sensor.

+ +

The designs aren’t without flaws, however. The main shortcoming of the circuits +is that they draw significant amounts of quiescent currents despite employing +sleep modes. The linear regulators were a poor choice as they dissipate too +much heat. The fingerprint sensor and the servo draw 13.8mA (3.3V) and 4.6mA +(5V) respectively, as long as they are connected to the power supply.

+ +

Although the circuit didn’t draw more than 200mA without a load, the servo +under load could draw up to 600mA. I’m sailing too close to the wind with 0.3mm +copper traces. Instead, 0.4mm wide 2oz/ft2 traces would have been +safer.

+ +

I’m working on improving the design to reduce idle current consumption and +extend the battery life. Despite its deficiencies, this was my first PCB +design, and I’m glad that it worked as well as it did. Custom PCB design marks +an important milestone in my DIY electronics journey.

+ +

Files: gerber_back.zip, gerber_front.zip, + source.tar.gz

diff --git a/_log/_site/my-first-pcb/back.jpeg b/_log/_site/my-first-pcb/back.jpeg new file mode 100644 index 0000000..f458e69 Binary files /dev/null and b/_log/_site/my-first-pcb/back.jpeg differ diff --git a/_log/_site/my-first-pcb/back_design.jpeg b/_log/_site/my-first-pcb/back_design.jpeg new file mode 100644 index 0000000..b6c0f5d Binary files /dev/null and b/_log/_site/my-first-pcb/back_design.jpeg differ diff --git a/_log/_site/my-first-pcb/front.jpeg b/_log/_site/my-first-pcb/front.jpeg new file mode 100644 index 0000000..2b2931f Binary files /dev/null and b/_log/_site/my-first-pcb/front.jpeg differ diff --git a/_log/_site/my-first-pcb/front_design.jpeg b/_log/_site/my-first-pcb/front_design.jpeg new file mode 100644 index 0000000..f81f09c Binary files /dev/null and b/_log/_site/my-first-pcb/front_design.jpeg differ diff --git a/_log/_site/my-first-pcb/gerber_back.zip b/_log/_site/my-first-pcb/gerber_back.zip new file mode 100644 index 0000000..26659ad Binary files /dev/null and b/_log/_site/my-first-pcb/gerber_back.zip differ diff --git a/_log/_site/my-first-pcb/gerber_front.zip b/_log/_site/my-first-pcb/gerber_front.zip new file mode 100644 index 0000000..864334e Binary files /dev/null and b/_log/_site/my-first-pcb/gerber_front.zip differ diff --git a/_log/_site/my-first-pcb/source.tar.gz b/_log/_site/my-first-pcb/source.tar.gz new file mode 100644 index 0000000..c31aa22 Binary files /dev/null and b/_log/_site/my-first-pcb/source.tar.gz differ diff --git a/_log/_site/my-first-pcb/thumb_sm.jpeg b/_log/_site/my-first-pcb/thumb_sm.jpeg new file mode 100644 index 0000000..c275b12 Binary files /dev/null and b/_log/_site/my-first-pcb/thumb_sm.jpeg differ diff --git a/_log/_site/neo4j-a-star-search.html b/_log/_site/neo4j-a-star-search.html new file mode 100644 index 0000000..9903abc --- /dev/null +++ b/_log/_site/neo4j-a-star-search.html @@ -0,0 +1,307 @@ +

Back in 2018, we used Neo4J graph database to track the +movement of marine vessels. We were interested in the shortest path a ship +could take through a network of about 13,000 route points. Graph theoretic +algorithms provide optimal solutions to such problems, and the set of route +points lends itself well to graph-based modelling.

+ +

A graph is a finite set of vertices, and a subset of vertex pairs (edges). +Edges can have weights. In the case of vessel tracking, the route points form +the vertices of a graph; the routes between them the edges; and the distances +between them the weights. For various reasons, people are interested in +minimizing (or maximizing) the weight of a path through a set of vertices, such +as the shortest path between two ports to predict a vessel’s arrival time.

+ +

Given a graph, an algorithm like Dijkstra’s search could compute the shortest +path between two vertices. In fact, this was the algorithm Neo4J shipped with +at the time. One drawback of Dijkstra’s algorithm is that it computes all the +shortest paths from the source to all other vertices before terminating at the +destination vertex. The time complexity of this exhaustive search prevented our +database from scaling beyond 4,000 route points.

+ +

The following enhancement to Dijkstra’s search, also known as the A* search, +employs a heuristic to steer the search in the direction of the destination +more quickly. In the case of our network of vessels, which are on the earth’s +surface, spherical distance is a good candidate for a heuristic:

+ +
package org.neo4j.graphalgo.impl;
+
+import java.util.stream.Stream;
+import java.util.stream.StreamSupport;
+
+import org.neo4j.graphalgo.api.Graph;
+import org.neo4j.graphalgo.core.utils.ProgressLogger;
+import org.neo4j.graphalgo.core.utils.queue.IntPriorityQueue;
+import org.neo4j.graphalgo.core.utils.queue.SharedIntPriorityQueue;
+import org.neo4j.graphalgo.core.utils.traverse.SimpleBitSet;
+import org.neo4j.graphdb.Direction;
+import org.neo4j.graphdb.Node;
+import org.neo4j.kernel.internal.GraphDatabaseAPI;
+
+import com.carrotsearch.hppc.IntArrayDeque;
+import com.carrotsearch.hppc.IntDoubleMap;
+import com.carrotsearch.hppc.IntDoubleScatterMap;
+import com.carrotsearch.hppc.IntIntMap;
+import com.carrotsearch.hppc.IntIntScatterMap;
+
+public class ShortestPathAStar extends Algorithm<ShortestPathAStar> {
+    
+    private final GraphDatabaseAPI dbService;
+    private static final int PATH_END = -1;
+    
+    private Graph graph;
+    private final int nodeCount;
+    private IntDoubleMap gCosts;
+    private IntDoubleMap fCosts;
+    private double totalCost;
+    private IntPriorityQueue openNodes;
+    private IntIntMap path;
+    private IntArrayDeque shortestPath;
+    private SimpleBitSet closedNodes;
+    private final ProgressLogger progressLogger;
+    
+    public static final double NO_PATH_FOUND = -1.0;
+    
+    public ShortestPathAStar(
+        final Graph graph,
+        final GraphDatabaseAPI dbService) {
+
+        this.graph = graph;
+        this.dbService = dbService;
+
+        nodeCount = Math.toIntExact(graph.nodeCount());
+        gCosts = new IntDoubleScatterMap(nodeCount);
+        fCosts = new IntDoubleScatterMap(nodeCount);
+        openNodes = SharedIntPriorityQueue.min(
+            nodeCount,
+            fCosts,
+            Double.MAX_VALUE);
+        path = new IntIntScatterMap(nodeCount);
+        closedNodes = new SimpleBitSet(nodeCount);
+        shortestPath = new IntArrayDeque();
+        progressLogger = getProgressLogger();
+    }
+    
+    public ShortestPathAStar compute(
+        final long startNode,
+        final long goalNode,
+        final String propertyKeyLat,
+        final String propertyKeyLon,
+        final Direction direction) {
+
+        reset();
+
+        final int startNodeInternal = 
+            graph.toMappedNodeId(startNode);
+        final double startNodeLat =
+            getNodeCoordinate(startNodeInternal, propertyKeyLat);
+        final double startNodeLon = 
+            getNodeCoordinate(startNodeInternal, propertyKeyLon);
+
+        final int goalNodeInternal =
+            graph.toMappedNodeId(goalNode);
+        final double goalNodeLat = 
+            getNodeCoordinate(goalNodeInternal, propertyKeyLat);
+        final double goalNodeLon = 
+            getNodeCoordinate(goalNodeInternal, propertyKeyLon);
+
+        final double initialHeuristic = 
+            computeHeuristic(startNodeLat,
+                startNodeLon,
+                goalNodeLat,
+                goalNodeLon);
+
+        gCosts.put(startNodeInternal, 0.0);
+        fCosts.put(startNodeInternal, initialHeuristic);
+        openNodes.add(startNodeInternal, 0.0);
+
+        run(goalNodeInternal,
+            propertyKeyLat,
+            propertyKeyLon,
+            direction);
+
+        if (path.containsKey(goalNodeInternal)) {
+            totalCost = gCosts.get(goalNodeInternal);
+            int node = goalNodeInternal;
+            while (node != PATH_END) {
+                shortestPath.addFirst(node);
+                node = path.getOrDefault(node, PATH_END);
+            }
+        }
+        return this;
+    }
+    
+    private void run(
+        final int goalNodeId,
+        final String propertyKeyLat,
+        final String propertyKeyLon,
+        final Direction direction) {
+
+        final double goalLat = 
+            getNodeCoordinate(goalNodeId, propertyKeyLat);
+        final double goalLon =
+            getNodeCoordinate(goalNodeId, propertyKeyLon);
+
+        while (!openNodes.isEmpty() && running()) {
+            int currentNodeId = openNodes.pop();
+            if (currentNodeId == goalNodeId) {
+                return;
+            }
+
+            closedNodes.put(currentNodeId);
+
+            double currentNodeCost = 
+                this.gCosts.getOrDefault(
+                    currentNodeId, 
+                    Double.MAX_VALUE);
+
+            graph.forEachRelationship(
+                currentNodeId,
+                direction,
+                (source, target, relationshipId, weight) -> {
+                    double neighbourLat = 
+                        getNodeCoordinate(target, propertyKeyLat);
+                    double neighbourLon = 
+                        getNodeCoordinate(target, propertyKeyLon);
+                    double heuristic = 
+                        computeHeuristic(
+                            neighbourLat, 
+                            neighbourLon, 
+                            goalLat,
+                            goalLon);
+
+                    updateCosts(
+                        source,
+                        target,
+                        weight + currentNodeCost,
+                        heuristic);
+
+                    if (!closedNodes.contains(target)) {
+                        openNodes.add(target, 0);
+                    }
+                    return true;
+                });
+
+            progressLogger.logProgress(
+                (double) currentNodeId / (nodeCount - 1));
+        }
+    }
+    
+    private double computeHeuristic(
+        final double lat1,
+        final double lon1,
+        final double lat2,
+        final double lon2) {
+
+        final int earthRadius = 6371;
+        final double kmToNM = 0.539957;
+        final double latDistance = Math.toRadians(lat2 - lat1);
+        final double lonDistance = Math.toRadians(lon2 - lon1);
+        final double a = Math.sin(latDistance / 2)
+            * Math.sin(latDistance / 2)
+            + Math.cos(Math.toRadians(lat1))
+            * Math.cos(Math.toRadians(lat2))
+            * Math.sin(lonDistance / 2)
+            * Math.sin(lonDistance / 2);
+        final double c = 2
+            * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
+        final double distance = earthRadius * c * kmToNM;
+        return distance;
+    }
+    
+    private double getNodeCoordinate(
+        final int nodeId,
+        final String coordinateType) {
+
+        final long neo4jId = graph.toOriginalNodeId(nodeId);
+        final Node node = dbService.getNodeById(neo4jId);
+        return (double) node.getProperty(coordinateType);
+    }
+    
+    private void updateCosts(
+        final int source, 
+        final int target, 
+        final double newCost,
+        final double heuristic) {
+
+        final double oldCost = 
+            gCosts.getOrDefault(target, Double.MAX_VALUE);
+
+        if (newCost < oldCost) {
+            gCosts.put(target, newCost);
+            fCosts.put(target, newCost + heuristic);
+            path.put(target, source);
+        }
+    }
+    
+    private void reset() {
+        closedNodes.clear();
+        openNodes.clear();
+        gCosts.clear();
+        fCosts.clear();
+        path.clear();
+        shortestPath.clear();
+        totalCost = NO_PATH_FOUND;
+    }
+    
+    public Stream<Result> resultStream() {
+        return StreamSupport.stream(
+            shortestPath.spliterator(), false)
+                .map(cursor -> new Result(
+                    graph.toOriginalNodeId(cursor.value),
+                    gCosts.get(cursor.value)));
+    }
+
+    public IntArrayDeque getFinalPath() {
+        return shortestPath;
+    }
+    
+    public double getTotalCost() {
+        return totalCost;
+    }
+
+    public int getPathLength() {
+        return shortestPath.size();
+    }
+    
+    @Override
+    public ShortestPathAStar me() {
+        return this;
+    }
+
+    @Override
+    public ShortestPathAStar release() {
+        graph = null;
+        gCosts = null;
+        fCosts = null;
+        openNodes = null;
+        path = null;
+        shortestPath = null;
+        closedNodes = null;
+        return this;
+    }
+    
+    public static class Result {
+
+        /**
+         * the neo4j node id
+         */
+        public final Long nodeId;
+
+        /**
+         * cost to reach the node from startNode
+         */
+        public final Double cost;
+
+        public Result(Long nodeId, Double cost) {
+            this.nodeId = nodeId;
+            this.cost = cost;
+        }
+    }
+}
+
+ +

The heuristic function is domain-specific. If chosen wisely, it can +significantly speed up the search. In our case, we achieved a 300x speedup, +enabling us to expand our search from 4,000 to 13,000 route points. The v3.4.0 of the +Neo4J graph algorithms shipped with our A* search algorithm.

+ diff --git a/_log/_site/robots.txt b/_log/_site/robots.txt new file mode 100644 index 0000000..e087884 --- /dev/null +++ b/_log/_site/robots.txt @@ -0,0 +1 @@ +Sitemap: /sitemap.xml diff --git a/_log/_site/sitemap.xml b/_log/_site/sitemap.xml new file mode 100644 index 0000000..8c167bd --- /dev/null +++ b/_log/_site/sitemap.xml @@ -0,0 +1,36 @@ + + + +/arduino-due.html + + +/arduino-uno.html + + +/bumblebee.html + + +/e-reader.html + + +/etlas.html + + +/fpm-door-lock.html + + +/matrix-digital-rain.html + + +/mosfet-switches.html + + +/my-first-pcb.html + + +/neo4j-a-star-search.html + + +/suckless-software.html + + diff --git a/_log/_site/suckless-software.html b/_log/_site/suckless-software.html new file mode 100644 index 0000000..d91ed16 --- /dev/null +++ b/_log/_site/suckless-software.html @@ -0,0 +1,78 @@ +

Since suckless software requires users to modify the +source code and recompile to customize, I need a way to maintain patches over +the long term while retaining the ability to upgrade the software as new +versions are released.

+ +

Initial setup

+ +

When using a suckless program, I usually begin by cloning the project and +setting the remote push URL to my own git repository:

+ +
git clone git://git.suckless.org/dwm
+git reset --hard <tag>
+git remote set-url --push origin git@git.asciimx.com:/repos/dwm
+
+ +

This way, I can pull updates from the upstream project whenever I want, while +committing my changes to my git repository. The git reset command aligns my +branch head with a stable release before applying patches or installing the +software.

+ +

If all I want to do is reconfigure the software (e.g., change key bindings), +which is what I need most of the time, the recommended approach is to modify +the config.h file. If the config.h isn’t yet in the project, the +make clean <target> command will generate it from the defaults and compile +the software. The <target> is the name of the application (e.g., dwm) found +in the Makefile. I modify the resulting config.h file and run make clean +install to install the software before committing and pushing my changes to +the git repo.

+ +

dwm and slstatus

+ +

Since dwm and slstatus are always running, make install will likely fail for +them. The operating system may prevent the installer from replacing running +executables with new ones. Hence, we must first stop the running instances of +these programs (in my case, using Mod + Shift + q). Then, switch to a tty +(Ctrl + Alt + F1), log in, and change the directory to where dwm/slstatus is. +We can run make install to install the software and switch back to the +graphical session (Ctrl + Alt + F5).

+ +

The key combinations for switching to the tty and back may differ across +systems. The ones listed above are for OpenBSD.

+ +

Subsequent upgrades

+ +

When suckless releases a new version, I run git pull --rebase to fetch the +upstream changes and rebase my patches on top of them. Because I tend to use +stable versions, I perform another interactive rebase to drop the commits +between the latest stable version tag and my patch before installing the +software.

+ +

Commit log before upgrading:

+ +
dt236  My patch.
+3fkdf  Version 6.5.
+
+ +

Commit log after pulling:

+ +
w467d  My patch.
+gh25g  A commit.
+g525g  Another commit.
+3fkdf  Version 6.6.
+vd425  Old commit.
+q12vu  Another old commit.
+3fkdf  Version 6.5.
+
+ +

Commit log after the interactive rebase:

+ +
h57jh  My patch.
+3fkdf  Version 6.6.
+vd425  Old commit.
+q12vu  Another old commit.
+3fkdf  Version 6.5.
+
+ +

And finally, I commit and push all the changes to my git repository.

+ diff --git a/_log/matrix-digital-rain.md b/_log/matrix-digital-rain.md index 2c35361..8c97ed3 100644 --- a/_log/matrix-digital-rain.md +++ b/_log/matrix-digital-rain.md @@ -6,43 +6,62 @@ project: true thumbnail: thumb_sm.png --- -The Matrix digital rain implemented in raw C using ANSI escape sequences with -zero dependencies—not even ncurses. +My 2022 implementation of the Matrix rain had too many loose ends. Unicode +support was inflexible: the charset had to be a single contiguous block with no +way to mix ASCII with something like Katakana; Phosphor decay level was stored +in a dedicated array--still don't understand why I did that when I had already +used bit-packing for the RGB channels; The algorithm was difficult to decipher. +The 2022 version worked, but that’s not the same thing as being correct. - +I began by placing the decay factor in the LSB of the 4-byte RGB value. Let's +call that RGB-PD. PD plays a somewhat analogous role to an alpha channel; I +avoided labelling it A so as not to cause confusion: + +``` +enum { + R, /* Red */ + G, /* Green */ + B, /* Blue */ + PD /* Phosphor decay level */ +}; -This is a fork of Domsson's unique rendition of the Matrix rain: Fakesteak. Three years ago, I forked his project -and added truecolor and Unicode support. I also drastically modified the -algorithm to produce a rain that resembled the original aesthetic with high -visual fidelity. +typedef union color_tag { + uint32_t value; + unsigned char color[4]; +} color; +``` -## Unicode support +The decision to use union over more portable bit twiddling was made three years +ago, as I recall, for readability. Seeing as all my systems are little-endian, +this is unlikely to cause me trouble. Besides, if union is never to be used, +why is it in the language anyway? -Unicode support in the 2022 version lacked flexibility. The charset used in the -rain had to be a single contiguous block defined by `UNICODE_MIN` and -`UNICODE_MAX` settings: +The blend() function, which emulates the dim afterglow of Phosphor by eroding +the RGB channels towards the background, remains as elegant as it did three +years ago: ``` -#define UNICODE_MIN 0x0021 -#define UNICODE_MAX 0x007E +#define DECAY_MPLIER 2 -static inline void insert_code(matrix *mat, - size_t row, size_t col) +static inline void blend(matrix *mat, + size_t row, size_t col) { - mat->code[index(mat, row, col)] = rand() - % (UNICODE_MAX - UNICODE_MIN) - + UNICODE_MIN; + unsigned char *color; + + color = mat->rgb[index(mat, row, col)].color; + color[R] = color[R] - (color[R] - RGB_BG_RED) / DECAY_MPLIER; + color[G] = color[G] - (color[G] - RGB_BG_GRN) / DECAY_MPLIER; + color[B] = color[B] - (color[B] - RGB_BG_BLU) / DECAY_MPLIER; } ``` -There was no way, for instance, to use both ASCII and Katakana at the same -time. The user had to pick one. In the new version, the user can use any number -of Unicode blocks using `glyphs` array. In fact, the default rain now includes -both ASCII and half-width Katakana characters: +While the memory inefficiency of Phosphor decay tracking was a technical +oversight I hadn't noticed, the limitation around mixing nonadjacent Unicode +blocks was a nagging concern even three years ago. So, a fix was long overdue. + +In the new version, I introduced a glyphs array that enables a user to add as +many Unicode blocks as they want. The insert_code() function picks a block +from the array at random, and then picks a character from that block at random: ``` #define UNICODE(min, max) (((uint64_t)max << 32) | min) @@ -70,50 +89,30 @@ static inline void insert_code(matrix *mat, } ``` -Entries in the `glyphs` array are Unicode blocks bit-packed in an 8-byte -container: the four low bytes forms the first codepoint and the four high bytes -the last. - -## Phosphor decay +The Unicode blocks are stored in 8-byte containers: the low four bytes form the +first codepoint and the high four bytes the last. Here, I chose bitwise +operations over unions because, first and foremost, the operations themselves +are trivial and idiomatic, and the UNICODE() macro simplifies the management of +charsets. The insert_code() function is now ready to take its rightful place +next to blend(). -The dim afterglow of monochrome CRT displays is achieved by carefully scaling -the RGB channels individually and mixing them: - -``` -#define DECAY_MPLIER 2 - -static inline void blend(matrix *mat, - size_t row, size_t col) -{ - unsigned char *color; - - color = mat->rgb[index(mat, row, col)].color; - color[R] = color[R] - (color[R] - RGB_BG_RED) / DECAY_MPLIER; - color[G] = color[G] - (color[G] - RGB_BG_GRN) / DECAY_MPLIER; - color[B] = color[B] - (color[B] - RGB_BG_BLU) / DECAY_MPLIER; -} -``` - -The blending function emulates the phosphor decay by gradually transitioning -each raindrop's color towards the background color. The multiplier is the -number of passes over the rain track needed before the afterglow disappears. - -## The algorithm - -Nonetheless, the rain resembles the original with high visual fidelity. It's -highly customizable and gentle on the CPU. On my 14" ThinkPad T490, which has a -resolution of 1920x1080 and 4GHz CPU, it uses 2-3% of the CPU with occasional -jumps of up to about 8%. Not too bad for a weekend project. The program has -been tested with xterm and urxvt terminal emulators on OpenBSD and Arch Linux -systems. Someone has managed to get it moving on a Raspberry Pi as well. - -Lastly, to compile and run: +The result is a digital rain that captures the original Matrix aesthetic with +high visual fidelity: ``` $ cc -O3 main.c -o matrix $ ./matrix ``` -"All I see is blonde, brunette, red head." + + +There was no cause to measure the program's performance characteristics +precisely; it's gentle on the CPU. On my ThinkPad T490 running OpenBSD, which +has a resolution of 1920x1080, it uses about 2-3% of the CPU, with occasional +jumps of up to about 8%; the cores remain silent, the fans don't whir, the rain +falls in quiet. Files: [source.tar.gz](source.tar.gz) + diff --git a/_log/my-first-pcb.md b/_log/my-first-pcb.md index c380ea0..eced7e4 100644 --- a/_log/my-first-pcb.md +++ b/_log/my-first-pcb.md @@ -2,7 +2,6 @@ title: My first PCB date: 2025-04-26 layout: post -thumbnail: thumb_sm.jpeg --- In 2023, I started tinkering with DIY electronics as a hobby. Until now, I've diff --git a/_log/neo4j-a-star-search.md b/_log/neo4j-a-star-search.md new file mode 100644 index 0000000..8c7e26e --- /dev/null +++ b/_log/neo4j-a-star-search.md @@ -0,0 +1,317 @@ +--- +title: Neo4J A* search +date: 2018-03-06 +layout: post +--- + +Back in 2018, we used Neo4J graph database to track the +movement of marine vessels. We were interested in the shortest path a ship +could take through a network of about 13,000 route points. Graph theoretic +algorithms provide optimal solutions to such problems, and the set of route +points lends itself well to graph-based modelling. + +A graph is a finite set of vertices, and a subset of vertex pairs (edges). +Edges can have weights. In the case of vessel tracking, the route points form +the vertices of a graph; the routes between them the edges; and the distances +between them the weights. For various reasons, people are interested in +minimizing (or maximizing) the weight of a path through a set of vertices, such +as the shortest path between two ports to predict a vessel's arrival time. + +Given a graph, an algorithm like Dijkstra's search could compute the shortest +path between two vertices. In fact, this was the algorithm Neo4J shipped with +at the time. One drawback of Dijkstra's algorithm is that it computes all the +shortest paths from the source to all other vertices before terminating at the +destination vertex. The time complexity of this exhaustive search prevented our +database from scaling beyond 4,000 route points. + +The following enhancement to Dijkstra's search, also known as the A* search, +employs a heuristic to steer the search in the direction of the destination +more quickly. In the case of our network of vessels, which are on the earth's +surface, spherical distance is a good candidate for a heuristic: + +``` +package org.neo4j.graphalgo.impl; + +import java.util.stream.Stream; +import java.util.stream.StreamSupport; + +import org.neo4j.graphalgo.api.Graph; +import org.neo4j.graphalgo.core.utils.ProgressLogger; +import org.neo4j.graphalgo.core.utils.queue.IntPriorityQueue; +import org.neo4j.graphalgo.core.utils.queue.SharedIntPriorityQueue; +import org.neo4j.graphalgo.core.utils.traverse.SimpleBitSet; +import org.neo4j.graphdb.Direction; +import org.neo4j.graphdb.Node; +import org.neo4j.kernel.internal.GraphDatabaseAPI; + +import com.carrotsearch.hppc.IntArrayDeque; +import com.carrotsearch.hppc.IntDoubleMap; +import com.carrotsearch.hppc.IntDoubleScatterMap; +import com.carrotsearch.hppc.IntIntMap; +import com.carrotsearch.hppc.IntIntScatterMap; + +public class ShortestPathAStar extends Algorithm { + + private final GraphDatabaseAPI dbService; + private static final int PATH_END = -1; + + private Graph graph; + private final int nodeCount; + private IntDoubleMap gCosts; + private IntDoubleMap fCosts; + private double totalCost; + private IntPriorityQueue openNodes; + private IntIntMap path; + private IntArrayDeque shortestPath; + private SimpleBitSet closedNodes; + private final ProgressLogger progressLogger; + + public static final double NO_PATH_FOUND = -1.0; + + public ShortestPathAStar( + final Graph graph, + final GraphDatabaseAPI dbService) { + + this.graph = graph; + this.dbService = dbService; + + nodeCount = Math.toIntExact(graph.nodeCount()); + gCosts = new IntDoubleScatterMap(nodeCount); + fCosts = new IntDoubleScatterMap(nodeCount); + openNodes = SharedIntPriorityQueue.min( + nodeCount, + fCosts, + Double.MAX_VALUE); + path = new IntIntScatterMap(nodeCount); + closedNodes = new SimpleBitSet(nodeCount); + shortestPath = new IntArrayDeque(); + progressLogger = getProgressLogger(); + } + + public ShortestPathAStar compute( + final long startNode, + final long goalNode, + final String propertyKeyLat, + final String propertyKeyLon, + final Direction direction) { + + reset(); + + final int startNodeInternal = + graph.toMappedNodeId(startNode); + final double startNodeLat = + getNodeCoordinate(startNodeInternal, propertyKeyLat); + final double startNodeLon = + getNodeCoordinate(startNodeInternal, propertyKeyLon); + + final int goalNodeInternal = + graph.toMappedNodeId(goalNode); + final double goalNodeLat = + getNodeCoordinate(goalNodeInternal, propertyKeyLat); + final double goalNodeLon = + getNodeCoordinate(goalNodeInternal, propertyKeyLon); + + final double initialHeuristic = + computeHeuristic(startNodeLat, + startNodeLon, + goalNodeLat, + goalNodeLon); + + gCosts.put(startNodeInternal, 0.0); + fCosts.put(startNodeInternal, initialHeuristic); + openNodes.add(startNodeInternal, 0.0); + + run(goalNodeInternal, + propertyKeyLat, + propertyKeyLon, + direction); + + if (path.containsKey(goalNodeInternal)) { + totalCost = gCosts.get(goalNodeInternal); + int node = goalNodeInternal; + while (node != PATH_END) { + shortestPath.addFirst(node); + node = path.getOrDefault(node, PATH_END); + } + } + return this; + } + + private void run( + final int goalNodeId, + final String propertyKeyLat, + final String propertyKeyLon, + final Direction direction) { + + final double goalLat = + getNodeCoordinate(goalNodeId, propertyKeyLat); + final double goalLon = + getNodeCoordinate(goalNodeId, propertyKeyLon); + + while (!openNodes.isEmpty() && running()) { + int currentNodeId = openNodes.pop(); + if (currentNodeId == goalNodeId) { + return; + } + + closedNodes.put(currentNodeId); + + double currentNodeCost = + this.gCosts.getOrDefault( + currentNodeId, + Double.MAX_VALUE); + + graph.forEachRelationship( + currentNodeId, + direction, + (source, target, relationshipId, weight) -> { + double neighbourLat = + getNodeCoordinate(target, propertyKeyLat); + double neighbourLon = + getNodeCoordinate(target, propertyKeyLon); + double heuristic = + computeHeuristic( + neighbourLat, + neighbourLon, + goalLat, + goalLon); + + updateCosts( + source, + target, + weight + currentNodeCost, + heuristic); + + if (!closedNodes.contains(target)) { + openNodes.add(target, 0); + } + return true; + }); + + progressLogger.logProgress( + (double) currentNodeId / (nodeCount - 1)); + } + } + + private double computeHeuristic( + final double lat1, + final double lon1, + final double lat2, + final double lon2) { + + final int earthRadius = 6371; + final double kmToNM = 0.539957; + final double latDistance = Math.toRadians(lat2 - lat1); + final double lonDistance = Math.toRadians(lon2 - lon1); + final double a = Math.sin(latDistance / 2) + * Math.sin(latDistance / 2) + + Math.cos(Math.toRadians(lat1)) + * Math.cos(Math.toRadians(lat2)) + * Math.sin(lonDistance / 2) + * Math.sin(lonDistance / 2); + final double c = 2 + * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a)); + final double distance = earthRadius * c * kmToNM; + return distance; + } + + private double getNodeCoordinate( + final int nodeId, + final String coordinateType) { + + final long neo4jId = graph.toOriginalNodeId(nodeId); + final Node node = dbService.getNodeById(neo4jId); + return (double) node.getProperty(coordinateType); + } + + private void updateCosts( + final int source, + final int target, + final double newCost, + final double heuristic) { + + final double oldCost = + gCosts.getOrDefault(target, Double.MAX_VALUE); + + if (newCost < oldCost) { + gCosts.put(target, newCost); + fCosts.put(target, newCost + heuristic); + path.put(target, source); + } + } + + private void reset() { + closedNodes.clear(); + openNodes.clear(); + gCosts.clear(); + fCosts.clear(); + path.clear(); + shortestPath.clear(); + totalCost = NO_PATH_FOUND; + } + + public Stream resultStream() { + return StreamSupport.stream( + shortestPath.spliterator(), false) + .map(cursor -> new Result( + graph.toOriginalNodeId(cursor.value), + gCosts.get(cursor.value))); + } + + public IntArrayDeque getFinalPath() { + return shortestPath; + } + + public double getTotalCost() { + return totalCost; + } + + public int getPathLength() { + return shortestPath.size(); + } + + @Override + public ShortestPathAStar me() { + return this; + } + + @Override + public ShortestPathAStar release() { + graph = null; + gCosts = null; + fCosts = null; + openNodes = null; + path = null; + shortestPath = null; + closedNodes = null; + return this; + } + + public static class Result { + + /** + * the neo4j node id + */ + public final Long nodeId; + + /** + * cost to reach the node from startNode + */ + public final Double cost; + + public Result(Long nodeId, Double cost) { + this.nodeId = nodeId; + this.cost = cost; + } + } +} +``` + +The heuristic function is domain-specific. If chosen wisely, it can +significantly speed up the search. In our case, we achieved a 300x speedup, +enabling us to expand our search from 4,000 to 13,000 route points. The v3.4.0 of the +Neo4J graph algorithms shipped with our A* search algorithm. + -- cgit v1.2.3