From 752a06ec0ebf20d6232b13f1ea53fe21fefcefbd Mon Sep 17 00:00:00 2001 From: Sadeep Madurange Date: Mon, 8 Dec 2025 17:34:35 +0800 Subject: Fix list indentation. --- _site/blog/arduino-due/connections.jpeg | Bin 0 -> 29090 bytes _site/blog/arduino-due/index.html | 172 +++++++++++++ _site/blog/arduino-due/schematic.png | Bin 0 -> 68688 bytes _site/blog/arduino-due/source.tar.gz | Bin 0 -> 1174 bytes _site/blog/arduino-uno/3v3.Makefile | 46 ++++ _site/blog/arduino-uno/Makefile | 43 ++++ _site/blog/arduino-uno/breadboard.jpeg | Bin 0 -> 54319 bytes _site/blog/arduino-uno/index.html | 139 +++++++++++ _site/blog/arduino-uno/pinout.png | Bin 0 -> 247197 bytes _site/blog/index.html | 129 ++++++++++ _site/blog/mosfet-switches/bjt.png | Bin 0 -> 12838 bytes _site/blog/mosfet-switches/index.html | 173 ++++++++++++++ _site/blog/mosfet-switches/n_high_side.png | Bin 0 -> 10825 bytes _site/blog/mosfet-switches/p_high_side.png | Bin 0 -> 10724 bytes _site/blog/neo4j-a-star-search/index.html | 371 +++++++++++++++++++++++++++++ _site/blog/suckless-software/index.html | 142 +++++++++++ 16 files changed, 1215 insertions(+) create mode 100644 _site/blog/arduino-due/connections.jpeg create mode 100644 _site/blog/arduino-due/index.html create mode 100644 _site/blog/arduino-due/schematic.png create mode 100644 _site/blog/arduino-due/source.tar.gz create mode 100644 _site/blog/arduino-uno/3v3.Makefile create mode 100644 _site/blog/arduino-uno/Makefile create mode 100644 _site/blog/arduino-uno/breadboard.jpeg create mode 100644 _site/blog/arduino-uno/index.html create mode 100644 _site/blog/arduino-uno/pinout.png create mode 100644 _site/blog/index.html create mode 100644 _site/blog/mosfet-switches/bjt.png create mode 100644 _site/blog/mosfet-switches/index.html create mode 100644 _site/blog/mosfet-switches/n_high_side.png create mode 100644 _site/blog/mosfet-switches/p_high_side.png create mode 100644 _site/blog/neo4j-a-star-search/index.html create mode 100644 _site/blog/suckless-software/index.html (limited to '_site/blog') diff --git a/_site/blog/arduino-due/connections.jpeg b/_site/blog/arduino-due/connections.jpeg new file mode 100644 index 0000000..081e6d4 Binary files /dev/null and b/_site/blog/arduino-due/connections.jpeg differ diff --git a/_site/blog/arduino-due/index.html b/_site/blog/arduino-due/index.html new file mode 100644 index 0000000..fee442f --- /dev/null +++ b/_site/blog/arduino-due/index.html @@ -0,0 +1,172 @@ + + + + + How to set up ATSAM3X8E microcontrollers for bare-metal programming in C + + + + + How to set up ATSAM3X8E microcontrollers for bare-metal programming in C + + + + + + + + + + + + + +
+
+
+

HOW TO SET UP ATSAM3X8E MICROCONTROLLERS FOR BARE-METAL PROGRAMMING IN C

+
05 OCTOBER 2024
+
+

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 initializes 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/_site/blog/arduino-due/schematic.png b/_site/blog/arduino-due/schematic.png new file mode 100644 index 0000000..62ddadd Binary files /dev/null and b/_site/blog/arduino-due/schematic.png differ diff --git a/_site/blog/arduino-due/source.tar.gz b/_site/blog/arduino-due/source.tar.gz new file mode 100644 index 0000000..496567b Binary files /dev/null and b/_site/blog/arduino-due/source.tar.gz differ diff --git a/_site/blog/arduino-uno/3v3.Makefile b/_site/blog/arduino-uno/3v3.Makefile new file mode 100644 index 0000000..4ca89d4 --- /dev/null +++ b/_site/blog/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/_site/blog/arduino-uno/Makefile b/_site/blog/arduino-uno/Makefile new file mode 100644 index 0000000..9db7b09 --- /dev/null +++ b/_site/blog/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/_site/blog/arduino-uno/breadboard.jpeg b/_site/blog/arduino-uno/breadboard.jpeg new file mode 100644 index 0000000..bd74907 Binary files /dev/null and b/_site/blog/arduino-uno/breadboard.jpeg differ diff --git a/_site/blog/arduino-uno/index.html b/_site/blog/arduino-uno/index.html new file mode 100644 index 0000000..7c4a71b --- /dev/null +++ b/_site/blog/arduino-uno/index.html @@ -0,0 +1,139 @@ + + + + + How to configure ATmega328P microcontrollers to run at 3.3V and 5V + + + + + How to configure ATmega328P microcontrollers to run at 3.3V and 5V + + + + + + + + + + + + + +
+
+
+

HOW TO CONFIGURE ATMEGA328P MICROCONTROLLERS TO RUN AT 3.3V AND 5V

+
10 APRIL 2025
+
+

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/_site/blog/arduino-uno/pinout.png b/_site/blog/arduino-uno/pinout.png new file mode 100644 index 0000000..59acfbc Binary files /dev/null and b/_site/blog/arduino-uno/pinout.png differ diff --git a/_site/blog/index.html b/_site/blog/index.html new file mode 100644 index 0000000..c213ee5 --- /dev/null +++ b/_site/blog/index.html @@ -0,0 +1,129 @@ + + + + + + + Blog + + + + + + + + + + + + +
+ +

Blog

+ +
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ +
+ +
+ +
+ +
+ +
+
+ + +
+
+ + + + + + diff --git a/_site/blog/mosfet-switches/bjt.png b/_site/blog/mosfet-switches/bjt.png new file mode 100644 index 0000000..9858fa7 Binary files /dev/null and b/_site/blog/mosfet-switches/bjt.png differ diff --git a/_site/blog/mosfet-switches/index.html b/_site/blog/mosfet-switches/index.html new file mode 100644 index 0000000..ed63e0a --- /dev/null +++ b/_site/blog/mosfet-switches/index.html @@ -0,0 +1,173 @@ + + + + + MOSFETs as electronic switches + + + + + MOSFETs as electronic switches + + + + + + + + + + + + + +
+
+
+

MOSFETS AS ELECTRONIC SWITCHES

+
22 JUNE 2025
+
+

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/_site/blog/mosfet-switches/n_high_side.png b/_site/blog/mosfet-switches/n_high_side.png new file mode 100644 index 0000000..c851768 Binary files /dev/null and b/_site/blog/mosfet-switches/n_high_side.png differ diff --git a/_site/blog/mosfet-switches/p_high_side.png b/_site/blog/mosfet-switches/p_high_side.png new file mode 100644 index 0000000..9f5397a Binary files /dev/null and b/_site/blog/mosfet-switches/p_high_side.png differ diff --git a/_site/blog/neo4j-a-star-search/index.html b/_site/blog/neo4j-a-star-search/index.html new file mode 100644 index 0000000..0d918c7 --- /dev/null +++ b/_site/blog/neo4j-a-star-search/index.html @@ -0,0 +1,371 @@ + + + + + Neo4J A* search + + + + + Neo4J A* search + + + + + + + + + + + + + +
+
+
+

NEO4J A* SEARCH

+
14 SEPTEMBER 2025
+
+

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. Algorithms based on +graph theory, such as A* search, provide optimal solutions to such problems. +In other words, the set of route points lends itself well to a model based on +graphs.

+ +

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 are the weights. For different reasons, people are interested in +minimizing (or maximizing) the weight of a path through a set of vertices. For +instance, we may want to find the shortest path between two ports.

+ +

Given such 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 exhaustive nature of this search +limited our search to about 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 the A* search algorithm.

+ +
+ +
+
+
+ + + + + + diff --git a/_site/blog/suckless-software/index.html b/_site/blog/suckless-software/index.html new file mode 100644 index 0000000..ea91072 --- /dev/null +++ b/_site/blog/suckless-software/index.html @@ -0,0 +1,142 @@ + + + + + How I manage Suckless software packages + + + + + How I manage Suckless software packages + + + + + + + + + + + + + +
+
+
+

HOW I MANAGE SUCKLESS SOFTWARE PACKAGES

+
30 NOVEMBER 2025
+
+

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 URL to push a copy of the source code with my patches 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 own 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 following +command generates it from the defaults and compiles the software using make +clean <target> here <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 my +git repo.

+ +

dwm and slstatus

+ +

Since dwm and slstatus are always running, make install will likely fail for +them. The operating system will prevent the installer from replacing running +executables with new ones. Hence, we must first stop the running instances of +these programs (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, commit and push all the changes to my own git repository.

+ +
+ +
+
+
+ + + + + + -- cgit v1.2.3