diff options
Diffstat (limited to '_archive')
| -rw-r--r-- | _archive/arduino-due.md | 122 | ||||
| -rw-r--r-- | _archive/arduino-due/connections.jpeg | bin | 29090 -> 0 bytes | |||
| -rw-r--r-- | _archive/arduino-due/schematic.png | bin | 68688 -> 0 bytes | |||
| -rw-r--r-- | _archive/arduino-due/source.tar.gz | bin | 1174 -> 0 bytes | |||
| -rw-r--r-- | _archive/arduino-uno.md | 82 | ||||
| -rw-r--r-- | _archive/arduino-uno/3v3.Makefile | 46 | ||||
| -rw-r--r-- | _archive/arduino-uno/Makefile | 43 | ||||
| -rw-r--r-- | _archive/arduino-uno/breadboard.jpeg | bin | 54319 -> 0 bytes | |||
| -rw-r--r-- | _archive/arduino-uno/pinout.png | bin | 247197 -> 0 bytes | |||
| -rw-r--r-- | _archive/mosfet-switches.md | 123 | ||||
| -rw-r--r-- | _archive/mosfet-switches/bjt.png | bin | 12838 -> 0 bytes | |||
| -rw-r--r-- | _archive/mosfet-switches/n_high_side.png | bin | 10825 -> 0 bytes | |||
| -rw-r--r-- | _archive/mosfet-switches/p_high_side.png | bin | 10724 -> 0 bytes | |||
| -rw-r--r-- | _archive/neo4j-a-star-search.md | 318 | ||||
| -rw-r--r-- | _archive/suckless-software.md | 90 |
15 files changed, 0 insertions, 824 deletions
diff --git a/_archive/arduino-due.md b/_archive/arduino-due.md deleted file mode 100644 index 7c0fb12..0000000 --- a/_archive/arduino-due.md +++ /dev/null @@ -1,122 +0,0 @@ ---- -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 <a -href="https://www.st.com/en/development-tools/st-link-v2.html" class="external" -target="_blank" rel="noopener noreferrer">ST-LINK/V2</a> programmer fits this -bill. - -The <a href="https://openocd.org/" class="external" target="_blank" -rel="noopener noreferrer">OpenOCD</a> 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 <a -href="https://developer.arm.com/Tools%20and%20Software/GNU%20Toolchain" -class="external" target="_blank" rel="noopener noreferrer">ARM GNU Compiler -Toolchain</a> 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. - -<table style="border: none; width: 100%;"> - <tr style="border: none;"> - <td style="border: none; width: 50%; vertical-align: top; background-color: transparent;"> - <img src="schematic.png" alt="Pinout" style="width: 100%"> - <p style="text-align: center;">Wiring</p> - </td> - <td style="border: none; width: 50%; vertical-align: top; background-color: transparent;"> - <img src="connections.jpeg" alt="Circuit" style="width: 100%"> - <p style="text-align: center;">Arduino Due</p> - </td> - </tr> -</table> - -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/_archive/arduino-due/connections.jpeg b/_archive/arduino-due/connections.jpeg Binary files differdeleted file mode 100644 index 081e6d4..0000000 --- a/_archive/arduino-due/connections.jpeg +++ /dev/null diff --git a/_archive/arduino-due/schematic.png b/_archive/arduino-due/schematic.png Binary files differdeleted file mode 100644 index 62ddadd..0000000 --- a/_archive/arduino-due/schematic.png +++ /dev/null diff --git a/_archive/arduino-due/source.tar.gz b/_archive/arduino-due/source.tar.gz Binary files differdeleted file mode 100644 index 496567b..0000000 --- a/_archive/arduino-due/source.tar.gz +++ /dev/null diff --git a/_archive/arduino-uno.md b/_archive/arduino-uno.md deleted file mode 100644 index 6534c3c..0000000 --- a/_archive/arduino-uno.md +++ /dev/null @@ -1,82 +0,0 @@ ---- -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. - -<table style="border: none; width: 100%;"> - <tr style="border: none;"> - <td style="border: none; width: 50%; vertical-align: top;"> - <img src="pinout.png" alt="Pinout" style="width: 100%"> - <p style="text-align: center;">Pinout</p> - </td> - <td style="border: none; width: 50%; vertical-align: top;"> - <img src="breadboard.jpeg" alt="Circuit" style="width: 100%"> - <p style="text-align: center;">Breadboard</p> - </td> - </tr> -</table> - -## 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 V<sub>CC</sub> 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 AV<sub>cc</sub> voltage as reference, do -not connect AREF (pin 21) to V<sub>cc</sub>. Refer to section 23.5.2 in the -datasheet for more information. - diff --git a/_archive/arduino-uno/3v3.Makefile b/_archive/arduino-uno/3v3.Makefile deleted file mode 100644 index 4ca89d4..0000000 --- a/_archive/arduino-uno/3v3.Makefile +++ /dev/null @@ -1,46 +0,0 @@ -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/_archive/arduino-uno/Makefile b/_archive/arduino-uno/Makefile deleted file mode 100644 index 9db7b09..0000000 --- a/_archive/arduino-uno/Makefile +++ /dev/null @@ -1,43 +0,0 @@ -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/_archive/arduino-uno/breadboard.jpeg b/_archive/arduino-uno/breadboard.jpeg Binary files differdeleted file mode 100644 index bd74907..0000000 --- a/_archive/arduino-uno/breadboard.jpeg +++ /dev/null diff --git a/_archive/arduino-uno/pinout.png b/_archive/arduino-uno/pinout.png Binary files differdeleted file mode 100644 index 59acfbc..0000000 --- a/_archive/arduino-uno/pinout.png +++ /dev/null diff --git a/_archive/mosfet-switches.md b/_archive/mosfet-switches.md deleted file mode 100644 index bb3514d..0000000 --- a/_archive/mosfet-switches.md +++ /dev/null @@ -1,123 +0,0 @@ ---- -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 <a -href="https://electronics.stackexchange.com/users/292884/simon-fitch" -class="external" target="_blank" rel="noopener noreferrer">Simon Fitch</a>. - -## 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. - - - -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: - - - -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. - - - -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. <a -href="https://teachmetomake.wordpress.com/how-to-use-a-transistor-as-a-switch/" -class="external" target="_blank" rel="noopener noreferrer">"How to choose a -transistor as a switch"</a> 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 V<sub>GS</sub> potentials -required to achieve specified R<sub>DS(on)</sub> 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 - - - <a href="https://www.embeddedrelated.com/showarticle/98.php" - class="external" target="_blank" rel="noopener noreferrer">Different MOSFET - topologies</a> - - <a href="https://www.embeddedrelated.com/showarticle/809.php" - class="external" target="_blank" rel="noopener noreferrer">How to read - MOSFET datasheets</a> - - <a src="https://teachmetomake.wordpress.com/how-to-use-a-transistor-as-a-switch/" - class="external" target="_blank" rel="noopener noreferrer">How to use a - transistor as a switch</a> - - <a src="https://forum.digikey.com/t/guide-to-selecting-and-controlling-a-mosfet-for-3-3-vdc-logic-applications/42606" - class="external" target="_blank" rel="noopener noreferrer">Guide to - selecting and controlling a MOSFET for 3.3 VDC logic applications</a> - - <a src="https://forum.digikey.com/t/driving-a-large-relay-from-a-3-3-vdc-microcontroller-using-an-npn-darlington-transistor/41751" - class="external" target="_blank" rel="noopener noreferrer">Driving a large - relay from a 3.3 VDC microcontroller using an NPN Darlington transistor</a> diff --git a/_archive/mosfet-switches/bjt.png b/_archive/mosfet-switches/bjt.png Binary files differdeleted file mode 100644 index 9858fa7..0000000 --- a/_archive/mosfet-switches/bjt.png +++ /dev/null diff --git a/_archive/mosfet-switches/n_high_side.png b/_archive/mosfet-switches/n_high_side.png Binary files differdeleted file mode 100644 index c851768..0000000 --- a/_archive/mosfet-switches/n_high_side.png +++ /dev/null diff --git a/_archive/mosfet-switches/p_high_side.png b/_archive/mosfet-switches/p_high_side.png Binary files differdeleted file mode 100644 index 9f5397a..0000000 --- a/_archive/mosfet-switches/p_high_side.png +++ /dev/null diff --git a/_archive/neo4j-a-star-search.md b/_archive/neo4j-a-star-search.md deleted file mode 100644 index 117931b..0000000 --- a/_archive/neo4j-a-star-search.md +++ /dev/null @@ -1,318 +0,0 @@ ---- -title: Neo4J A* search -date: 2025-09-14 -layout: post ---- - -Back in 2018, we used <a href="https://neo4j.com/" class="external" -target="_blank" rel="noopener noreferrer">Neo4J</a> 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 <a -href="https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases/tag/3.4.0.0" -class="external" target="_blank" rel="noopener noreferrer">v3.4.0</a> of the -Neo4J graph algorithms shipped with the A* search algorithm. - diff --git a/_archive/suckless-software.md b/_archive/suckless-software.md deleted file mode 100644 index 86fb5bc..0000000 --- a/_archive/suckless-software.md +++ /dev/null @@ -1,90 +0,0 @@ ---- -title: How I manage Suckless software packages -date: 2025-11-30 -layout: post ---- - -Since <a href="https://suckless.org/" class="external" target="_blank" -rel="noopener noreferrer">suckless</a> 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. - |
