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. --- _blog/arduino-due.md | 122 +++++++++++++ _blog/arduino-due/connections.jpeg | Bin 0 -> 29090 bytes _blog/arduino-due/schematic.png | Bin 0 -> 68688 bytes _blog/arduino-due/source.tar.gz | Bin 0 -> 1174 bytes _blog/arduino-uno.md | 82 +++++++++ _blog/arduino-uno/3v3.Makefile | 46 +++++ _blog/arduino-uno/Makefile | 43 +++++ _blog/arduino-uno/breadboard.jpeg | Bin 0 -> 54319 bytes _blog/arduino-uno/pinout.png | Bin 0 -> 247197 bytes _blog/mosfet-switches.md | 123 +++++++++++++ _blog/mosfet-switches/bjt.png | Bin 0 -> 12838 bytes _blog/mosfet-switches/n_high_side.png | Bin 0 -> 10825 bytes _blog/mosfet-switches/p_high_side.png | Bin 0 -> 10724 bytes _blog/neo4j-a-star-search.md | 318 ++++++++++++++++++++++++++++++++++ _blog/suckless-software.md | 90 ++++++++++ 15 files changed, 824 insertions(+) create mode 100644 _blog/arduino-due.md create mode 100644 _blog/arduino-due/connections.jpeg create mode 100644 _blog/arduino-due/schematic.png create mode 100644 _blog/arduino-due/source.tar.gz create mode 100644 _blog/arduino-uno.md create mode 100644 _blog/arduino-uno/3v3.Makefile create mode 100644 _blog/arduino-uno/Makefile create mode 100644 _blog/arduino-uno/breadboard.jpeg create mode 100644 _blog/arduino-uno/pinout.png create mode 100644 _blog/mosfet-switches.md create mode 100644 _blog/mosfet-switches/bjt.png create mode 100644 _blog/mosfet-switches/n_high_side.png create mode 100644 _blog/mosfet-switches/p_high_side.png create mode 100644 _blog/neo4j-a-star-search.md create mode 100644 _blog/suckless-software.md (limited to '_blog') diff --git a/_blog/arduino-due.md b/_blog/arduino-due.md new file mode 100644 index 0000000..7c0fb12 --- /dev/null +++ b/_blog/arduino-due.md @@ -0,0 +1,122 @@ +--- +title: How to set up ATSAM3X8E microcontrollers for bare-metal programming in C +date: 2024-10-05 +layout: post +--- + +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](source.tar.gz) diff --git a/_blog/arduino-due/connections.jpeg b/_blog/arduino-due/connections.jpeg new file mode 100644 index 0000000..081e6d4 Binary files /dev/null and b/_blog/arduino-due/connections.jpeg differ diff --git a/_blog/arduino-due/schematic.png b/_blog/arduino-due/schematic.png new file mode 100644 index 0000000..62ddadd Binary files /dev/null and b/_blog/arduino-due/schematic.png differ diff --git a/_blog/arduino-due/source.tar.gz b/_blog/arduino-due/source.tar.gz new file mode 100644 index 0000000..496567b Binary files /dev/null and b/_blog/arduino-due/source.tar.gz differ diff --git a/_blog/arduino-uno.md b/_blog/arduino-uno.md new file mode 100644 index 0000000..6534c3c --- /dev/null +++ b/_blog/arduino-uno.md @@ -0,0 +1,82 @@ +--- +title: How to configure ATmega328P microcontrollers to run at 3.3V and 5V +date: 2025-04-10 +layout: post +--- + +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](Makefile) 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](3v3.Makefile) 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/_blog/arduino-uno/3v3.Makefile b/_blog/arduino-uno/3v3.Makefile new file mode 100644 index 0000000..4ca89d4 --- /dev/null +++ b/_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/_blog/arduino-uno/Makefile b/_blog/arduino-uno/Makefile new file mode 100644 index 0000000..9db7b09 --- /dev/null +++ b/_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/_blog/arduino-uno/breadboard.jpeg b/_blog/arduino-uno/breadboard.jpeg new file mode 100644 index 0000000..bd74907 Binary files /dev/null and b/_blog/arduino-uno/breadboard.jpeg differ diff --git a/_blog/arduino-uno/pinout.png b/_blog/arduino-uno/pinout.png new file mode 100644 index 0000000..59acfbc Binary files /dev/null and b/_blog/arduino-uno/pinout.png differ diff --git a/_blog/mosfet-switches.md b/_blog/mosfet-switches.md new file mode 100644 index 0000000..bb3514d --- /dev/null +++ b/_blog/mosfet-switches.md @@ -0,0 +1,123 @@ +--- +title: MOSFETs as electronic switches +date: 2025-06-22 +layout: post +--- + +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](p_high_side.png) + +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](n_high_side.png) + +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](bjt.png) + +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 + + - Different MOSFET + topologies + - How to read + MOSFET datasheets + - How to use a + transistor as a switch + - Guide to + selecting and controlling a MOSFET for 3.3 VDC logic applications + - Driving a large + relay from a 3.3 VDC microcontroller using an NPN Darlington transistor diff --git a/_blog/mosfet-switches/bjt.png b/_blog/mosfet-switches/bjt.png new file mode 100644 index 0000000..9858fa7 Binary files /dev/null and b/_blog/mosfet-switches/bjt.png differ diff --git a/_blog/mosfet-switches/n_high_side.png b/_blog/mosfet-switches/n_high_side.png new file mode 100644 index 0000000..c851768 Binary files /dev/null and b/_blog/mosfet-switches/n_high_side.png differ diff --git a/_blog/mosfet-switches/p_high_side.png b/_blog/mosfet-switches/p_high_side.png new file mode 100644 index 0000000..9f5397a Binary files /dev/null and b/_blog/mosfet-switches/p_high_side.png differ diff --git a/_blog/neo4j-a-star-search.md b/_blog/neo4j-a-star-search.md new file mode 100644 index 0000000..117931b --- /dev/null +++ b/_blog/neo4j-a-star-search.md @@ -0,0 +1,318 @@ +--- +title: Neo4J A* search +date: 2025-09-14 +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. 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 { + + 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 the A* search algorithm. + diff --git a/_blog/suckless-software.md b/_blog/suckless-software.md new file mode 100644 index 0000000..86fb5bc --- /dev/null +++ b/_blog/suckless-software.md @@ -0,0 +1,90 @@ +--- +title: How I manage Suckless software packages +date: 2025-11-30 +layout: post +--- + +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 +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 ` here `` 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