diff options
| author | Sadeep Madurange <sadeep@asciimx.com> | 2025-10-25 18:19:48 +0800 |
|---|---|---|
| committer | Sadeep Madurange <sadeep@asciimx.com> | 2025-10-25 19:07:22 +0800 |
| commit | 8cd867cd53794386cb9443bfc023fe97c5c5fa47 (patch) | |
| tree | 0f3f076e8b7f542b511d737eaaf3f3ec1cef457d | |
| parent | 210a4c8671b368a3a240f9cb7a0bd1718a301523 (diff) | |
| download | www-8cd867cd53794386cb9443bfc023fe97c5c5fa47.tar.gz | |
Render posts.
53 files changed, 2106 insertions, 72 deletions
diff --git a/_archive/arduino-due.md b/_archive/arduino-due.md new file mode 100644 index 0000000..0551376 --- /dev/null +++ b/_archive/arduino-due.md @@ -0,0 +1,112 @@ +--- +title: Bare-metal ARM Cortex M3 chips +date: 2024-10-05 +author: W. D. Sadeep Madurange +layout: post +--- + +This post is about programming bare metal SAM3X8E Arm Cortex M3 chips found on +Arduino Due boards. I had to learn how to do this because none of the +high-level tools for programming Arduino Dues are available for OpenBSD, which +I use for much of my personal computing. + +## Toolchain + +Since we will not be using pre-packaged development tools, we need to assemble +our own toolchain. As usual, we need a compiler toolchain to build programs for +the target chip. As we will be bypassing the embedded bootloader, we will also +need a hardware programmer and an on-chip debugger to flash programs to the +chip. I used the following toolchain. + +- <a href="https://developer.arm.com/Tools%20and%20Software/GNU%20Toolchain" + class="external" target="_blank" rel="noopener noreferrer">Arm GNU compiler + toolchain</a>. +- <a href="https://openocd.org/" class="external" target="_blank" + rel="noopener noreferrer">OpenOCD</a> on-chip debugger. +- <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. + +## Electrical connections + +The following diagram outlines the electrical connections between the different +components necessary to move 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 SAM3X8E's Serial Wire Debug (SWD) interface via its +DEBUG port. The ST-LINK/v2 programmer uses the SWD protocol to communicate with +the chip. + +## Uploading the program + +Follow the steps below to upload a program to the SAM3X8E chip. The +source.tar.gz tarball at the end of the page contains a sample program with a +OpenOCD config file and a linker script. + + 1. Start OpenOCD: + ``` + $ openocd -f openocd-due.cfg + ``` + 2. Open a telnet session and check that the GPNVM1 bit is set. Otherwise + set it to 1: + + ``` + $ telnet localhost 4444 + > halt + > at91sam3 gpnvm show + > at91sam3 gpnvm set 1 + > at91sam3 gpnvm show + ``` + 3. Build the program using the custom linker script. + ``` + $ arm-none-eabi-gcc -mcpu=cortex-m3 -mthumb -T script.ld \ + -nostartfiles \ + -nostdlib \ + -o a.elf main.c + ``` + 4. Upload the program using OpenOCD: + ``` + $ openocd -f openocd-due.cfg -c "program a.elf verify reset exit" + ``` + +Refer to the OpenOCD manual (AT91SAM3 flash driver section) for a complete list +of commands supported for the ATSAM3X8E. + +## GPNVM bits and the linker script + +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 +(default), the chip boots from the ROM, which contains Atmel's SAM-BA +bootloader. So, the chip runs the embedded bootloader instead of our program. + +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 using the linker script, we set the GPNVM1 bit and +leave the GPNVM2 bit as it is. + +The linker script places the vector table at the first address of the flash. +ARM chips expect this unless we relocate the vector table using the VTOR +register. The first entry of the vector table must be the stack pointer, and +the second must be the reset vector. + +Finally, the ATSAM3X8E uses a descending stack. So, in the linker script, we +initialize the stack pointer to the highest memory location available. In the +reset vector, we zero out memory, initialize registers, and perform other tasks +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 differnew file mode 100644 index 0000000..081e6d4 --- /dev/null +++ b/_archive/arduino-due/connections.jpeg diff --git a/_archive/arduino-due/schematic.png b/_archive/arduino-due/schematic.png Binary files differnew file mode 100644 index 0000000..62ddadd --- /dev/null +++ b/_archive/arduino-due/schematic.png diff --git a/_archive/arduino-due/source.tar.gz b/_archive/arduino-due/source.tar.gz Binary files differnew file mode 100644 index 0000000..496567b --- /dev/null +++ b/_archive/arduino-due/source.tar.gz diff --git a/_archive/arduino-uno.md b/_archive/arduino-uno.md new file mode 100644 index 0000000..ec754e7 --- /dev/null +++ b/_archive/arduino-uno.md @@ -0,0 +1,66 @@ +--- +title: Notes on programming ATmega328P chips +date: 2025-04-10 +author: W. D. Sadeep Madurange +layout: post +--- + +This post is a step-by-step guide for wiring up ATmega328P ICs to run at 5 V +with a 16 MHz crystal and 3.3 V with an 8 MHz crystal. While the 5 V +configuration is common, the 3.3 V configuration can be advantageous in +low-power applications and when interfacing with parts that run at 3.3 V. + +## 5 V - 16 MHz configuration + +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> + + 1. Connect pin 1 to 5 V via a 10 kΩ resistor. + 2. Connect a 16 MHz crystal oscillator across pins 9 and 10. + 3. Connect each pin of the crystal to ground via 22 pF capacitors. + 4. Connect pins 7, 20, and 21 to 5 V. + 5. Connect pins 8 and 22 to ground. + +In addition to the connections described above, 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 avr-gcc and avrdude. + +## 3.3 V - 8 MHz configuration + +The following steps use Arduino Uno as an ISP and Arduino utilities to program +ATmega328P's bootloader and the fuses (e.g., BOD level) for a 3.3 V supply. + + 1. Upload the 'ArduinoISP' sketch to the Uno. + 2. Wire up the ATmega328P as described in the previous section. Replace the 5 V + supply with a 3.3 V supply and use an 8 MHz crystal instead of the 16 MHz + crystal. + 3. Connect the SPI ports (SCK, MISO, and MOSI) of the two MCUs. + 4. Connect Uno's SS pin to the IC's pin 1 (RESET). + 5. The IC can be powered by the Arduino Uno's 5 V pin. + 6. Burn the bootloader to the ATmega328P: + - Select 'ATmega328P (3.3 V, 8 MHz)' from Tools > Processor. + - Select 'Arduino as ISP' from Tools > Programmer. + - Select Tools > Burn Bootloader. + +The ATmega328P is now ready to run at 8 MHz with a 3.3 V power supply. You can +upload programs to the ATmega328P as you usually would using avrdude. +[Here's](3v3.Makefile) a sample Makefile with adjusted parameters (e.g., baud +rate) for an 8 MHz clock. + +In both configurations, if you intend to use the ATmega328P's analog-to-digital +converter with the internal 1.1 V 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 ADC +Voltage Reference in the datasheet for more information. + diff --git a/_archive/arduino-uno/3v3.Makefile b/_archive/arduino-uno/3v3.Makefile new file mode 100644 index 0000000..4ca89d4 --- /dev/null +++ b/_archive/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/_archive/arduino-uno/Makefile b/_archive/arduino-uno/Makefile new file mode 100644 index 0000000..9db7b09 --- /dev/null +++ b/_archive/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/_archive/arduino-uno/breadboard.jpeg b/_archive/arduino-uno/breadboard.jpeg Binary files differnew file mode 100644 index 0000000..bd74907 --- /dev/null +++ b/_archive/arduino-uno/breadboard.jpeg diff --git a/_archive/arduino-uno/pinout.png b/_archive/arduino-uno/pinout.png Binary files differnew file mode 100644 index 0000000..59acfbc --- /dev/null +++ b/_archive/arduino-uno/pinout.png diff --git a/_archive/awesome-books.md b/_archive/awesome-books.md new file mode 100644 index 0000000..887a39d --- /dev/null +++ b/_archive/awesome-books.md @@ -0,0 +1,89 @@ +--- +title: Awesome books +date: 2025-04-20 +author: W. D. Sadeep Madurange +layout: post +--- + +This article contains a list of my favourite books. + +## Cloud Atlas + +This highly creative novel rekindled my love of fiction. Cloud Atlas is a +collection of six tales linked across time. As the novel unfolds, each story +riffles over the previous ones, like a pack of playing cards. + +## Ender's Game + +In this sci-fi novel, Andrew "Ender" Wiggin, a young boy, is drafted to lead a +squad of young children in an offensive against an alien race. It's a complex +story that touches upon various political and philosophical issues. Those +perceived as gifted by others (and alienated for it) will likely connect with +Ender. + +## Flowers for Algernon + +This novel, written as a series of progress reports, tells the story of Charlie +Gordon, a developmentally disabled man who acquires superhuman cognitive +abilities through an experimental medical procedure. For some reason, I felt a +deep connection with Charlie. If I had to pick a favourite book on this list, +that would be this. + +## Dead Souls + +Nikolai Gogol is one of the most original authors I've read. Dead Souls is the +story of Ivanovich Chichikov, a traveling merchant who trades dead serfs. +Instead of simply describing them, Gogol develops realistic characters in +minute detail by employing theatrical clashes between them. + +## The Overcoat + +Gogol's The Overcoat is one of the finest short stories I've read. Akaky +Akakievich, an impoverished government clerk, must buy a new overcoat. I +recommend reading Gogol before Dostoyevsky. What Gogol invented, Dostoyevsky +perfected. + +## Demons + +After reading Demons, a story about an attempted revolution, I realized that +Dostoevsky’s reputation is well-deserved. Dostoyevsky was a great observer of +the human psyche. The depth with which he depicts his characters is +unparalleled. Demons is a book that anyone aspiring to bring about change +through revolution must read. + +## The Outsider + +Camus's quote, "In our society, any man who doesn't cry at his mother's funeral +is liable to be condemned to death," summarizes the book quite well. To +appreciate the philosophical elements of this absurdist novel, you may also +want to check out The Myth of Sisyphus. + +## Frankenstein + +I'm not sure why I found this story so charming. Perhaps it's a deep-felt +empathy for Victor Frankenstein. Maybe it's the rustic descriptions of places +I'd never seen. After reading the book, I traveled Frankenstein's trail from +Germany through Lucerne, Geneva, and Scotland. + +## Strange Case of Dr Jekyll and Mr Hyde + +The story of Dr Jekyll and Mr Hyde needs no introduction. I'm drawn to +Stevenson's writing style the same way I am to Mary Shelley's. Both writers +evoke deep feelings and paint vivid images using simple language. The economy +of their language lacks neither precision nor power. If I could write like any +author, I would choose Mary Shelley or Stevenson. + +## Brave New World and Nineteen Eighty-Four + +Huxley's Brave New World and Orwell's 1984 are inseparable, visionary novels +that depict dystopian futures from two extremes. For some reason, I felt Brave +New World lacked something despite being the more prescient of the two. It may +be Orwell's eloquence overshadowing Huxley's brilliance. In any event, these +two books are more relevant today than they've ever been. + +## Memoirs of a Madman + +Another one of Gogol's brilliant short stories. Presented in the form of +Aksenty Ivanovich's diary, the story documents the government clerk's descent +into madness. His obsession with social status and self-aggrandizement leads +him on a trajectory of envy, wounded pride, and outright insanity. diff --git a/_archive/mosfet-switches.md b/_archive/mosfet-switches.md new file mode 100644 index 0000000..dfabd9a --- /dev/null +++ b/_archive/mosfet-switches.md @@ -0,0 +1,124 @@ +--- +title: MOSFETs +date: 2025-06-22 +author: W. D. Sadeep Madurange +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 switch off power +to components, such as servos, electronically when not needed. That's how I +stumbled upon 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 transistors 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 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 differnew file mode 100644 index 0000000..9858fa7 --- /dev/null +++ b/_archive/mosfet-switches/bjt.png diff --git a/_archive/mosfet-switches/n_high_side.png b/_archive/mosfet-switches/n_high_side.png Binary files differnew file mode 100644 index 0000000..c851768 --- /dev/null +++ b/_archive/mosfet-switches/n_high_side.png diff --git a/_archive/mosfet-switches/p_high_side.png b/_archive/mosfet-switches/p_high_side.png Binary files differnew file mode 100644 index 0000000..9f5397a --- /dev/null +++ b/_archive/mosfet-switches/p_high_side.png diff --git a/_archive/my-first-pcb.md b/_archive/my-first-pcb.md new file mode 100644 index 0000000..20eaa10 --- /dev/null +++ b/_archive/my-first-pcb.md @@ -0,0 +1,64 @@ +--- +title: My first PCB +date: 2025-07-14 +author: W. D. Sadeep Madurange +layout: post +--- + +In 2023, I started tinkering with DIY electronics as a hobby. Until now, I've +been using development boards like the Arduino Uno and ESP-32-WROOM so that I +can focus on the software. Recently, I decided to step outside of my comfort +zone and design a PCB from scratch for a door lock I'm working on. + +The lock comprises two subsystems: a fingerprint sensor in front of the door +and a servo connected to the physical lock behind the door. The fingerprint +sensor authenticates the person and signals the servo behind the door to unlock +the door over an encrypted RF channel. + +<table style="border: none; width: 100%"> + <tr style="border: none;"> + <td style="border: none; width: 50%; vertical-align: top; text-align: center;"> + <img src="front_design.jpeg" alt="Design (front)" style="width: 100%"> + <p>Footprint (front)</p> + </td> + <td style="border: none; width: 50%; vertical-align: center; text-align: center;"> + <img src="front.jpeg" alt="PCB (front)" style="width: 100%"> + <p>PCB (front)</p> + </td> + </tr> + <tr style="border: none;"> + <td style="border: none; width: 50%; vertical-align: top; text-align: center;"> + <img src="back_design.jpeg" alt="Design (back)" style="width: 100%"> + <p>Footprint (back)</p> + </td> + <td style="border: none; width: 50%; vertical-align: center; text-align: center;"> + <img src="back.jpeg" alt="PCB (back)" style="width: 100%"> + <p>PCB (back)</p> + </td> + </tr> +</table> + +The PCBs have two layers. A copper region serves as the ground plane. The 0.3 +mm wide 1 oz/ft<sup>2</sup> copper traces can carry up to 500 mA (the tracks +connecting the power source and the linear regulators have a width of 0.5 mm). +Both subsystems were functional. I was able to control the servo reliably using +the fingerprint sensor. + +The designs aren't without flaws, however. The main shortcoming of the circuits +is that they draw significant amounts of quiescent currents despite employing +sleep modes. The linear regulators were a poor choice as they dissipate too +much heat. The fingerprint sensor and the servo draw 13.8 mA (3.3 V) and 4.6 mA +(5 V) respectively, as long as they are connected to the power supply. + +Although the circuit didn't draw more than 200 mA without a load, the servo +under load could draw up to 600 mA. I'm sailing too close to the wind with 0.3 +mm copper traces. Instead, 0.4 mm wide 2 oz/ft<sup>2</sup> traces would have +been safer. + +I'm working on improving the design to reduce idle current consumption and +extend the battery life. Despite its deficiencies, this was my first PCB +design, and I'm glad that it worked as well as it did. Custom PCB design marks +an important milestone in my DIY electronics journey. + +Files: [gerber_back.zip](gerber_back.zip), [gerber_front.zip](gerber_front.zip), + [source.tar.gz](source.tar.gz) diff --git a/_archive/my-first-pcb/back.jpeg b/_archive/my-first-pcb/back.jpeg Binary files differnew file mode 100644 index 0000000..f458e69 --- /dev/null +++ b/_archive/my-first-pcb/back.jpeg diff --git a/_archive/my-first-pcb/back_design.jpeg b/_archive/my-first-pcb/back_design.jpeg Binary files differnew file mode 100644 index 0000000..b6c0f5d --- /dev/null +++ b/_archive/my-first-pcb/back_design.jpeg diff --git a/_archive/my-first-pcb/front.jpeg b/_archive/my-first-pcb/front.jpeg Binary files differnew file mode 100644 index 0000000..2b2931f --- /dev/null +++ b/_archive/my-first-pcb/front.jpeg diff --git a/_archive/my-first-pcb/front_design.jpeg b/_archive/my-first-pcb/front_design.jpeg Binary files differnew file mode 100644 index 0000000..f81f09c --- /dev/null +++ b/_archive/my-first-pcb/front_design.jpeg diff --git a/_archive/my-first-pcb/gerber_back.zip b/_archive/my-first-pcb/gerber_back.zip Binary files differnew file mode 100644 index 0000000..26659ad --- /dev/null +++ b/_archive/my-first-pcb/gerber_back.zip diff --git a/_archive/my-first-pcb/gerber_front.zip b/_archive/my-first-pcb/gerber_front.zip Binary files differnew file mode 100644 index 0000000..864334e --- /dev/null +++ b/_archive/my-first-pcb/gerber_front.zip diff --git a/_archive/my-first-pcb/source.tar.gz b/_archive/my-first-pcb/source.tar.gz Binary files differnew file mode 100644 index 0000000..c31aa22 --- /dev/null +++ b/_archive/my-first-pcb/source.tar.gz diff --git a/_archive/neo4j-a-star-search.md b/_archive/neo4j-a-star-search.md new file mode 100644 index 0000000..c46121f --- /dev/null +++ b/_archive/neo4j-a-star-search.md @@ -0,0 +1,316 @@ +--- +title: Neo4J A* search +date: 2025-09-14 +author: Wickramage Don Sadeep Madurange +layout: post +--- + +Back in 2018, we used the <a src="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. +Performance issues with Neo4J’s then-available shortest-path algorithms limited +our search to about 4,000 route points. + +The fix led to my first contribution to an open-source project: + +``` +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; + } + } +} +``` + +If you are new to them, a graph is a finite set of vertices (such as ports +ships are known to travel through), and a subset of vertex pairs (such as +origin and destination ports) known as edges. + +Edges can have weights. In the case of ships and ports, the weights could be +the distances between ports. For various 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. + +There's nothing spectacular about the code. It is, for the most part, a patch +over Dijkstra's algorithm that employs spherical distance between vertices as a +heuristic to steer the search in the right direction. Dijkstra's algorithm, on +the other hand, explores all possible paths from the source, which is what +makes it slower. + +The heuristic function is domain-specific. I planned to make it configurable, +but didn't get around to it. With the help of my A* algorithm, we scaled our +search to include all the route points of interest. <a +href="https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases/tag/3.4.0.0" +class="external" target="_blank" rel="noopener noreferrer>Here's</a> a link to +the now-archived official release. + diff --git a/_blog/post-1/index.md b/_blog/post-1/index.md deleted file mode 100644 index 5b5beeb..0000000 --- a/_blog/post-1/index.md +++ /dev/null @@ -1,14 +0,0 @@ ---- -layout: default -author: jill -type: blog -date: 2025-10-23 ---- - -An apple is a sweet, edible fruit produced by an apple tree. - -Apple trees are cultivated worldwide, and are the most widely grown -species in the genus Malus. The tree originated in Central Asia, where -its wild ancestor, Malus sieversii, is still found today. Apples have -been grown for thousands of years in Asia and Europe, and were brought -to North America by European colonists. diff --git a/_config.yml b/_config.yml index 71ededd..f13b5c7 100644 --- a/_config.yml +++ b/_config.yml @@ -4,7 +4,7 @@ tagline: "Wickramage Don Sadeep's Personal Website" permalink: pretty collections: - blog: + archive: output: true projects: output: true diff --git a/_site/archive/arduino-due/connections.jpeg b/_site/archive/arduino-due/connections.jpeg Binary files differnew file mode 100644 index 0000000..081e6d4 --- /dev/null +++ b/_site/archive/arduino-due/connections.jpeg diff --git a/_site/archive/arduino-due/index.html b/_site/archive/arduino-due/index.html new file mode 100644 index 0000000..76baab0 --- /dev/null +++ b/_site/archive/arduino-due/index.html @@ -0,0 +1,158 @@ +<!DOCTYPE html> +<html> + <head> + <meta charset="utf-8"> + <title>Bare-metal ARM Cortex M3 chips</title> + <head> +<meta charset="utf-8"> + <title>Bare-metal ARM Cortex M3 chips</title> + <link rel="stylesheet" href="/assets/css/main.css"> + <link rel="stylesheet" href="/assets/css/normalize.css"> + <link rel="stylesheet" href="/assets/css/skeleton.css"> +</head> + + + </head> + <body> + + <div class="container"> + <ul id="navlist" class="left"> + + <li > + <a href="/">hme</a> + </li> + <li > + <a href="/projects/">proj</a> + </li> + <li > + <a href="/about/">abt</a> + </li> + <li><a href="/feed.xml">rss</a></li> + </ul> +</div> + + + + <main> + <div class="container"> + <h2 class="brand center" id="title">BARE-METAL ARM CORTEX M3 CHIPS</h2> + + <h6 class="center">05 OCTOBER 2024</h5> + + <br> + + <div class="threecol justify"><p>This post is about programming bare metal SAM3X8E Arm Cortex M3 chips found on +Arduino Due boards. I had to learn how to do this because none of the +high-level tools for programming Arduino Dues are available for OpenBSD, which +I use for much of my personal computing.</p> + +<h2 id="toolchain">Toolchain</h2> + +<p>Since we will not be using pre-packaged development tools, we need to assemble +our own toolchain. As usual, we need a compiler toolchain to build programs for +the target chip. As we will be bypassing the embedded bootloader, we will also +need a hardware programmer and an on-chip debugger to flash programs to the +chip. I used the following toolchain.</p> + +<ul> + <li><a href="https://developer.arm.com/Tools%20and%20Software/GNU%20Toolchain" class="external" target="_blank" rel="noopener noreferrer">Arm GNU compiler +toolchain</a>.</li> + <li><a href="https://openocd.org/" class="external" target="_blank" rel="noopener noreferrer">OpenOCD</a> on-chip debugger.</li> + <li><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.</li> +</ul> + +<h2 id="electrical-connections">Electrical connections</h2> + +<p>The following diagram outlines the electrical connections between the different +components necessary to move a compiled program from a PC to the MCU.</p> + +<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> + +<p>Arduino Due exposes the SAM3X8E’s Serial Wire Debug (SWD) interface via its +DEBUG port. The ST-LINK/v2 programmer uses the SWD protocol to communicate with +the chip.</p> + +<h2 id="uploading-the-program">Uploading the program</h2> + +<p>Follow the steps below to upload a program to the SAM3X8E chip. The +source.tar.gz tarball at the end of the page contains a sample program with a +OpenOCD config file and a linker script.</p> + +<ol> + <li>Start OpenOCD: + <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>$ openocd -f openocd-due.cfg +</code></pre></div> </div> + </li> + <li> + <p>Open a telnet session and check that the GPNVM1 bit is set. Otherwise +set it to 1:</p> + + <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>$ telnet localhost 4444 + > halt + > at91sam3 gpnvm show + > at91sam3 gpnvm set 1 + > at91sam3 gpnvm show +</code></pre></div> </div> + </li> + <li>Build the program using the custom linker script. + <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>$ arm-none-eabi-gcc -mcpu=cortex-m3 -mthumb -T script.ld \ + -nostartfiles \ + -nostdlib \ + -o a.elf main.c +</code></pre></div> </div> + </li> + <li>Upload the program using OpenOCD: + <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>$ openocd -f openocd-due.cfg -c "program a.elf verify reset exit" +</code></pre></div> </div> + </li> +</ol> + +<p>Refer to the OpenOCD manual (AT91SAM3 flash driver section) for a complete list +of commands supported for the ATSAM3X8E.</p> + +<h2 id="gpnvm-bits-and-the-linker-script">GPNVM bits and the linker script</h2> + +<p>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.</p> + +<p>The GPNVM bits control which of them maps to 0x00000. When GPNVM1 is cleared +(default), the chip boots from the ROM, which contains Atmel’s SAM-BA +bootloader. So, the chip runs the embedded bootloader instead of our program.</p> + +<p>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 using the linker script, we set the GPNVM1 bit and +leave the GPNVM2 bit as it is.</p> + +<p>The linker script places the vector table at the first address of the flash. +ARM chips expect this unless we relocate the vector table using the VTOR +register. The first entry of the vector table must be the stack pointer, and +the second must be the reset vector.</p> + +<p>Finally, the ATSAM3X8E uses a descending stack. So, in the linker script, we +initialize the stack pointer to the highest memory location available. In the +reset vector, we zero out memory, initialize registers, and perform other tasks +before passing control to the main program.</p> + +<p>Files: <a href="source.tar.gz">source.tar.gz</a></p> +</div> + + <p class="right italics">by W. D. Sadeep Madurange</p> + </div> + </main> + + </body> +</html> diff --git a/_site/archive/arduino-due/schematic.png b/_site/archive/arduino-due/schematic.png Binary files differnew file mode 100644 index 0000000..62ddadd --- /dev/null +++ b/_site/archive/arduino-due/schematic.png diff --git a/_site/archive/arduino-due/source.tar.gz b/_site/archive/arduino-due/source.tar.gz Binary files differnew file mode 100644 index 0000000..496567b --- /dev/null +++ b/_site/archive/arduino-due/source.tar.gz diff --git a/_site/archive/arduino-uno/3v3.Makefile b/_site/archive/arduino-uno/3v3.Makefile new file mode 100644 index 0000000..4ca89d4 --- /dev/null +++ b/_site/archive/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/archive/arduino-uno/Makefile b/_site/archive/arduino-uno/Makefile new file mode 100644 index 0000000..9db7b09 --- /dev/null +++ b/_site/archive/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/archive/arduino-uno/breadboard.jpeg b/_site/archive/arduino-uno/breadboard.jpeg Binary files differnew file mode 100644 index 0000000..bd74907 --- /dev/null +++ b/_site/archive/arduino-uno/breadboard.jpeg diff --git a/_site/archive/arduino-uno/index.html b/_site/archive/arduino-uno/index.html new file mode 100644 index 0000000..ff3ca44 --- /dev/null +++ b/_site/archive/arduino-uno/index.html @@ -0,0 +1,117 @@ +<!DOCTYPE html> +<html> + <head> + <meta charset="utf-8"> + <title>Notes on programming ATmega328P chips</title> + <head> +<meta charset="utf-8"> + <title>Notes on programming ATmega328P chips</title> + <link rel="stylesheet" href="/assets/css/main.css"> + <link rel="stylesheet" href="/assets/css/normalize.css"> + <link rel="stylesheet" href="/assets/css/skeleton.css"> +</head> + + + </head> + <body> + + <div class="container"> + <ul id="navlist" class="left"> + + <li > + <a href="/">hme</a> + </li> + <li > + <a href="/projects/">proj</a> + </li> + <li > + <a href="/about/">abt</a> + </li> + <li><a href="/feed.xml">rss</a></li> + </ul> +</div> + + + + <main> + <div class="container"> + <h2 class="brand center" id="title">NOTES ON PROGRAMMING ATMEGA328P CHIPS</h2> + + <h6 class="center">10 APRIL 2025</h5> + + <br> + + <div class="threecol justify"><p>This post is a step-by-step guide for wiring up ATmega328P ICs to run at 5 V +with a 16 MHz crystal and 3.3 V with an 8 MHz crystal. While the 5 V +configuration is common, the 3.3 V configuration can be advantageous in +low-power applications and when interfacing with parts that run at 3.3 V.</p> + +<h2 id="5-v---16-mhz-configuration">5 V - 16 MHz configuration</h2> + +<p>The steps that follow refer to the following pinout.</p> + +<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> + +<ol> + <li>Connect pin 1 to 5 V via a 10 kΩ resistor.</li> + <li>Connect a 16 MHz crystal oscillator across pins 9 and 10.</li> + <li>Connect each pin of the crystal to ground via 22 pF capacitors.</li> + <li>Connect pins 7, 20, and 21 to 5 V.</li> + <li>Connect pins 8 and 22 to ground.</li> +</ol> + +<p>In addition to the connections described above, it’s a good idea to add 0.1 μF +decoupling capacitors between pins 7, 20, and 21 and ground. +<a href="Makefile">Here’s</a> a sample Makefile for avr-gcc and avrdude.</p> + +<h2 id="33-v---8-mhz-configuration">3.3 V - 8 MHz configuration</h2> + +<p>The following steps use Arduino Uno as an ISP and Arduino utilities to program +ATmega328P’s bootloader and the fuses (e.g., BOD level) for a 3.3 V supply.</p> + +<ol> + <li>Upload the ‘ArduinoISP’ sketch to the Uno.</li> + <li>Wire up the ATmega328P as described in the previous section. Replace the 5 V +supply with a 3.3 V supply and use an 8 MHz crystal instead of the 16 MHz +crystal.</li> + <li>Connect the SPI ports (SCK, MISO, and MOSI) of the two MCUs.</li> + <li>Connect Uno’s SS pin to the IC’s pin 1 (RESET).</li> + <li>The IC can be powered by the Arduino Uno’s 5 V pin.</li> + <li>Burn the bootloader to the ATmega328P: + <ul> + <li>Select ‘ATmega328P (3.3 V, 8 MHz)’ from Tools > Processor.</li> + <li>Select ‘Arduino as ISP’ from Tools > Programmer.</li> + <li>Select Tools > Burn Bootloader.</li> + </ul> + </li> +</ol> + +<p>The ATmega328P is now ready to run at 8 MHz with a 3.3 V power supply. You can +upload programs to the ATmega328P as you usually would using avrdude. +<a href="3v3.Makefile">Here’s</a> a sample Makefile with adjusted parameters (e.g., baud +rate) for an 8 MHz clock.</p> + +<p>In both configurations, if you intend to use the ATmega328P’s analog-to-digital +converter with the internal 1.1 V 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 ADC +Voltage Reference in the datasheet for more information.</p> + +</div> + + <p class="right italics">by W. D. Sadeep Madurange</p> + </div> + </main> + + </body> +</html> diff --git a/_site/archive/arduino-uno/pinout.png b/_site/archive/arduino-uno/pinout.png Binary files differnew file mode 100644 index 0000000..59acfbc --- /dev/null +++ b/_site/archive/arduino-uno/pinout.png diff --git a/_site/archive/awesome-books/index.html b/_site/archive/awesome-books/index.html new file mode 100644 index 0000000..9abdc5d --- /dev/null +++ b/_site/archive/awesome-books/index.html @@ -0,0 +1,133 @@ +<!DOCTYPE html> +<html> + <head> + <meta charset="utf-8"> + <title>Awesome books</title> + <head> +<meta charset="utf-8"> + <title>Awesome books</title> + <link rel="stylesheet" href="/assets/css/main.css"> + <link rel="stylesheet" href="/assets/css/normalize.css"> + <link rel="stylesheet" href="/assets/css/skeleton.css"> +</head> + + + </head> + <body> + + <div class="container"> + <ul id="navlist" class="left"> + + <li > + <a href="/">hme</a> + </li> + <li > + <a href="/projects/">proj</a> + </li> + <li > + <a href="/about/">abt</a> + </li> + <li><a href="/feed.xml">rss</a></li> + </ul> +</div> + + + + <main> + <div class="container"> + <h2 class="brand center" id="title">AWESOME BOOKS</h2> + + <h6 class="center">20 APRIL 2025</h5> + + <br> + + <div class="threecol justify"><p>This article contains a list of my favourite books.</p> + +<h2 id="cloud-atlas">Cloud Atlas</h2> + +<p>This highly creative novel rekindled my love of fiction. Cloud Atlas is a +collection of six tales linked across time. As the novel unfolds, each story +riffles over the previous ones, like a pack of playing cards.</p> + +<h2 id="enders-game">Ender’s Game</h2> + +<p>In this sci-fi novel, Andrew “Ender” Wiggin, a young boy, is drafted to lead a +squad of young children in an offensive against an alien race. It’s a complex +story that touches upon various political and philosophical issues. Those +perceived as gifted by others (and alienated for it) will likely connect with +Ender.</p> + +<h2 id="flowers-for-algernon">Flowers for Algernon</h2> + +<p>This novel, written as a series of progress reports, tells the story of Charlie +Gordon, a developmentally disabled man who acquires superhuman cognitive +abilities through an experimental medical procedure. For some reason, I felt a +deep connection with Charlie. If I had to pick a favourite book on this list, +that would be this.</p> + +<h2 id="dead-souls">Dead Souls</h2> + +<p>Nikolai Gogol is one of the most original authors I’ve read. Dead Souls is the +story of Ivanovich Chichikov, a traveling merchant who trades dead serfs. +Instead of simply describing them, Gogol develops realistic characters in +minute detail by employing theatrical clashes between them.</p> + +<h2 id="the-overcoat">The Overcoat</h2> + +<p>Gogol’s The Overcoat is one of the finest short stories I’ve read. Akaky +Akakievich, an impoverished government clerk, must buy a new overcoat. I +recommend reading Gogol before Dostoyevsky. What Gogol invented, Dostoyevsky +perfected.</p> + +<h2 id="demons">Demons</h2> + +<p>After reading Demons, a story about an attempted revolution, I realized that +Dostoevsky’s reputation is well-deserved. Dostoyevsky was a great observer of +the human psyche. The depth with which he depicts his characters is +unparalleled. Demons is a book that anyone aspiring to bring about change +through revolution must read.</p> + +<h2 id="the-outsider">The Outsider</h2> + +<p>Camus’s quote, “In our society, any man who doesn’t cry at his mother’s funeral +is liable to be condemned to death,” summarizes the book quite well. To +appreciate the philosophical elements of this absurdist novel, you may also +want to check out The Myth of Sisyphus.</p> + +<h2 id="frankenstein">Frankenstein</h2> + +<p>I’m not sure why I found this story so charming. Perhaps it’s a deep-felt +empathy for Victor Frankenstein. Maybe it’s the rustic descriptions of places +I’d never seen. After reading the book, I traveled Frankenstein’s trail from +Germany through Lucerne, Geneva, and Scotland.</p> + +<h2 id="strange-case-of-dr-jekyll-and-mr-hyde">Strange Case of Dr Jekyll and Mr Hyde</h2> + +<p>The story of Dr Jekyll and Mr Hyde needs no introduction. I’m drawn to +Stevenson’s writing style the same way I am to Mary Shelley’s. Both writers +evoke deep feelings and paint vivid images using simple language. The economy +of their language lacks neither precision nor power. If I could write like any +author, I would choose Mary Shelley or Stevenson.</p> + +<h2 id="brave-new-world-and-nineteen-eighty-four">Brave New World and Nineteen Eighty-Four</h2> + +<p>Huxley’s Brave New World and Orwell’s 1984 are inseparable, visionary novels +that depict dystopian futures from two extremes. For some reason, I felt Brave +New World lacked something despite being the more prescient of the two. It may +be Orwell’s eloquence overshadowing Huxley’s brilliance. In any event, these +two books are more relevant today than they’ve ever been.</p> + +<h2 id="memoirs-of-a-madman">Memoirs of a Madman</h2> + +<p>Another one of Gogol’s brilliant short stories. Presented in the form of +Aksenty Ivanovich’s diary, the story documents the government clerk’s descent +into madness. His obsession with social status and self-aggrandizement leads +him on a trajectory of envy, wounded pride, and outright insanity.</p> +</div> + + <p class="right italics">by W. D. Sadeep Madurange</p> + </div> + </main> + + </body> +</html> diff --git a/_site/archive/mosfet-switches/bjt.png b/_site/archive/mosfet-switches/bjt.png Binary files differnew file mode 100644 index 0000000..9858fa7 --- /dev/null +++ b/_site/archive/mosfet-switches/bjt.png diff --git a/_site/archive/mosfet-switches/index.html b/_site/archive/mosfet-switches/index.html new file mode 100644 index 0000000..99e32ea --- /dev/null +++ b/_site/archive/mosfet-switches/index.html @@ -0,0 +1,161 @@ +<!DOCTYPE html> +<html> + <head> + <meta charset="utf-8"> + <title>MOSFETs</title> + <head> +<meta charset="utf-8"> + <title>MOSFETs</title> + <link rel="stylesheet" href="/assets/css/main.css"> + <link rel="stylesheet" href="/assets/css/normalize.css"> + <link rel="stylesheet" href="/assets/css/skeleton.css"> +</head> + + + </head> + <body> + + <div class="container"> + <ul id="navlist" class="left"> + + <li > + <a href="/">hme</a> + </li> + <li > + <a href="/projects/">proj</a> + </li> + <li > + <a href="/about/">abt</a> + </li> + <li><a href="/feed.xml">rss</a></li> + </ul> +</div> + + + + <main> + <div class="container"> + <h2 class="brand center" id="title">MOSFETS</h2> + + <h6 class="center">22 JUNE 2025</h5> + + <br> + + <div class="threecol justify"><p>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 switch off power +to components, such as servos, electronically when not needed. That’s how I +stumbled upon MOSFETs, transistors capable of controlling circuits operating at +voltages far above their own.</p> + +<h2 id="acknowledgments">Acknowledgments</h2> + +<p>This article is a summary of what I learnt about using transistors 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 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>.</p> + +<h2 id="preamble">Preamble</h2> + +<p>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).</p> + +<p>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> + +<h2 id="p-channel-high-side-switch">P-channel high-side switch</h2> + +<p>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> + +<p><img src="p_high_side.png" alt="P-channel high-side switching circuit" /></p> + +<p>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.</p> + +<h2 id="n-channel-high-side-switch">N-channel high-side switch</h2> + +<p>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:</p> + +<p><img src="n_high_side.png" alt="N-channel high-side switching circuit" /></p> + +<p>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.</p> + +<p>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.</p> + +<p>The D1 flyback diodes used in the two topologies safeguard the MOSFET from +voltage spikes caused by inductive loads such as servos.</p> + +<h2 id="a-bjt-alternative">A BJT alternative</h2> + +<p>A Bipolar Junction Transistor (BJT) is a simpler, cheaper, and more widely +available type of transistor that can be used as a switch.</p> + +<p><img src="bjt.png" alt="BJT architecture" /></p> + +<p>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.</p> + +<h2 id="which-topology-to-choose">Which topology to choose?</h2> + +<p>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).</p> + +<p>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.</p> + +<h2 id="further-reading">Further reading</h2> + +<ul> + <li><a href="https://www.embeddedrelated.com/showarticle/98.php" class="external" target="_blank" rel="noopener noreferrer">Different MOSFET +topologies</a></li> + <li><a href="https://www.embeddedrelated.com/showarticle/809.php" class="external" target="_blank" rel="noopener noreferrer">How to read +MOSFET datasheets</a></li> + <li><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></li> + <li><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></li> + <li><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></li> +</ul> +</div> + + <p class="right italics">by W. D. Sadeep Madurange</p> + </div> + </main> + + </body> +</html> diff --git a/_site/archive/mosfet-switches/n_high_side.png b/_site/archive/mosfet-switches/n_high_side.png Binary files differnew file mode 100644 index 0000000..c851768 --- /dev/null +++ b/_site/archive/mosfet-switches/n_high_side.png diff --git a/_site/archive/mosfet-switches/p_high_side.png b/_site/archive/mosfet-switches/p_high_side.png Binary files differnew file mode 100644 index 0000000..9f5397a --- /dev/null +++ b/_site/archive/mosfet-switches/p_high_side.png diff --git a/_site/archive/my-first-pcb/back.jpeg b/_site/archive/my-first-pcb/back.jpeg Binary files differnew file mode 100644 index 0000000..f458e69 --- /dev/null +++ b/_site/archive/my-first-pcb/back.jpeg diff --git a/_site/archive/my-first-pcb/back_design.jpeg b/_site/archive/my-first-pcb/back_design.jpeg Binary files differnew file mode 100644 index 0000000..b6c0f5d --- /dev/null +++ b/_site/archive/my-first-pcb/back_design.jpeg diff --git a/_site/archive/my-first-pcb/front.jpeg b/_site/archive/my-first-pcb/front.jpeg Binary files differnew file mode 100644 index 0000000..2b2931f --- /dev/null +++ b/_site/archive/my-first-pcb/front.jpeg diff --git a/_site/archive/my-first-pcb/front_design.jpeg b/_site/archive/my-first-pcb/front_design.jpeg Binary files differnew file mode 100644 index 0000000..f81f09c --- /dev/null +++ b/_site/archive/my-first-pcb/front_design.jpeg diff --git a/_site/archive/my-first-pcb/gerber_back.zip b/_site/archive/my-first-pcb/gerber_back.zip Binary files differnew file mode 100644 index 0000000..26659ad --- /dev/null +++ b/_site/archive/my-first-pcb/gerber_back.zip diff --git a/_site/archive/my-first-pcb/gerber_front.zip b/_site/archive/my-first-pcb/gerber_front.zip Binary files differnew file mode 100644 index 0000000..864334e --- /dev/null +++ b/_site/archive/my-first-pcb/gerber_front.zip diff --git a/_site/archive/my-first-pcb/index.html b/_site/archive/my-first-pcb/index.html new file mode 100644 index 0000000..69b809f --- /dev/null +++ b/_site/archive/my-first-pcb/index.html @@ -0,0 +1,108 @@ +<!DOCTYPE html> +<html> + <head> + <meta charset="utf-8"> + <title>My first PCB</title> + <head> +<meta charset="utf-8"> + <title>My first PCB</title> + <link rel="stylesheet" href="/assets/css/main.css"> + <link rel="stylesheet" href="/assets/css/normalize.css"> + <link rel="stylesheet" href="/assets/css/skeleton.css"> +</head> + + + </head> + <body> + + <div class="container"> + <ul id="navlist" class="left"> + + <li > + <a href="/">hme</a> + </li> + <li > + <a href="/projects/">proj</a> + </li> + <li > + <a href="/about/">abt</a> + </li> + <li><a href="/feed.xml">rss</a></li> + </ul> +</div> + + + + <main> + <div class="container"> + <h2 class="brand center" id="title">MY FIRST PCB</h2> + + <h6 class="center">14 JULY 2025</h5> + + <br> + + <div class="threecol justify"><p>In 2023, I started tinkering with DIY electronics as a hobby. Until now, I’ve +been using development boards like the Arduino Uno and ESP-32-WROOM so that I +can focus on the software. Recently, I decided to step outside of my comfort +zone and design a PCB from scratch for a door lock I’m working on.</p> + +<p>The lock comprises two subsystems: a fingerprint sensor in front of the door +and a servo connected to the physical lock behind the door. The fingerprint +sensor authenticates the person and signals the servo behind the door to unlock +the door over an encrypted RF channel.</p> + +<table style="border: none; width: 100%"> + <tr style="border: none;"> + <td style="border: none; width: 50%; vertical-align: top; text-align: center;"> + <img src="front_design.jpeg" alt="Design (front)" style="width: 100%" /> + <p>Footprint (front)</p> + </td> + <td style="border: none; width: 50%; vertical-align: center; text-align: center;"> + <img src="front.jpeg" alt="PCB (front)" style="width: 100%" /> + <p>PCB (front)</p> + </td> + </tr> + <tr style="border: none;"> + <td style="border: none; width: 50%; vertical-align: top; text-align: center;"> + <img src="back_design.jpeg" alt="Design (back)" style="width: 100%" /> + <p>Footprint (back)</p> + </td> + <td style="border: none; width: 50%; vertical-align: center; text-align: center;"> + <img src="back.jpeg" alt="PCB (back)" style="width: 100%" /> + <p>PCB (back)</p> + </td> + </tr> +</table> + +<p>The PCBs have two layers. A copper region serves as the ground plane. The 0.3 +mm wide 1 oz/ft<sup>2</sup> copper traces can carry up to 500 mA (the tracks +connecting the power source and the linear regulators have a width of 0.5 mm). +Both subsystems were functional. I was able to control the servo reliably using +the fingerprint sensor.</p> + +<p>The designs aren’t without flaws, however. The main shortcoming of the circuits +is that they draw significant amounts of quiescent currents despite employing +sleep modes. The linear regulators were a poor choice as they dissipate too +much heat. The fingerprint sensor and the servo draw 13.8 mA (3.3 V) and 4.6 mA +(5 V) respectively, as long as they are connected to the power supply.</p> + +<p>Although the circuit didn’t draw more than 200 mA without a load, the servo +under load could draw up to 600 mA. I’m sailing too close to the wind with 0.3 +mm copper traces. Instead, 0.4 mm wide 2 oz/ft<sup>2</sup> traces would have +been safer.</p> + +<p>I’m working on improving the design to reduce idle current consumption and +extend the battery life. Despite its deficiencies, this was my first PCB +design, and I’m glad that it worked as well as it did. Custom PCB design marks +an important milestone in my DIY electronics journey.</p> + +<p>Files: <a href="gerber_back.zip">gerber_back.zip</a>, <a href="gerber_front.zip">gerber_front.zip</a>, + <a href="source.tar.gz">source.tar.gz</a></p> +</div> + + <p class="right italics">by W. D. Sadeep Madurange</p> + </div> + </main> + + </body> +</html> diff --git a/_site/archive/my-first-pcb/source.tar.gz b/_site/archive/my-first-pcb/source.tar.gz Binary files differnew file mode 100644 index 0000000..c31aa22 --- /dev/null +++ b/_site/archive/my-first-pcb/source.tar.gz diff --git a/_site/archive/neo4j-a-star-search/index.html b/_site/archive/neo4j-a-star-search/index.html new file mode 100644 index 0000000..ca7579b --- /dev/null +++ b/_site/archive/neo4j-a-star-search/index.html @@ -0,0 +1,358 @@ +<!DOCTYPE html> +<html> + <head> + <meta charset="utf-8"> + <title>Neo4J A* search</title> + <head> +<meta charset="utf-8"> + <title>Neo4J A* search</title> + <link rel="stylesheet" href="/assets/css/main.css"> + <link rel="stylesheet" href="/assets/css/normalize.css"> + <link rel="stylesheet" href="/assets/css/skeleton.css"> +</head> + + + </head> + <body> + + <div class="container"> + <ul id="navlist" class="left"> + + <li > + <a href="/">hme</a> + </li> + <li > + <a href="/projects/">proj</a> + </li> + <li > + <a href="/about/">abt</a> + </li> + <li><a href="/feed.xml">rss</a></li> + </ul> +</div> + + + + <main> + <div class="container"> + <h2 class="brand center" id="title">NEO4J A* SEARCH</h2> + + <h6 class="center">14 SEPTEMBER 2025</h5> + + <br> + + <div class="threecol justify"><p>Back in 2018, we used the <a src="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. +Performance issues with Neo4J’s then-available shortest-path algorithms limited +our search to about 4,000 route points.</p> + +<p>The fix led to my first contribution to an open-source project:</p> + +<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>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; + } + } +} +</code></pre></div></div> + +<p>If you are new to them, a graph is a finite set of vertices (such as ports +ships are known to travel through), and a subset of vertex pairs (such as +origin and destination ports) known as edges.</p> + +<p>Edges can have weights. In the case of ships and ports, the weights could be +the distances between ports. For various 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.</p> + +<p>There’s nothing spectacular about the code. It is, for the most part, a patch +over Dijkstra’s algorithm that employs spherical distance between vertices as a +heuristic to steer the search in the right direction. Dijkstra’s algorithm, on +the other hand, explores all possible paths from the source, which is what +makes it slower.</p> + +<p>The heuristic function is domain-specific. I planned to make it configurable, +but didn’t get around to it. With the help of my A* algorithm, we scaled our +search to include all the route points of interest. <a +href=”https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases/tag/3.4.0.0” +class=”external” target=”_blank” rel=”noopener noreferrer>Here’s</a> a link to +the now-archived official release.</p> + +</div> + + <p class="right italics">by Wickramage Don Sadeep Madurange</p> + </div> + </main> + + </body> +</html> diff --git a/_site/assets/css/main.css b/_site/assets/css/main.css index fbc22f7..43afb69 100644 --- a/_site/assets/css/main.css +++ b/_site/assets/css/main.css @@ -217,3 +217,14 @@ and (min-device-width : 768px) { } } +.posts-td-time { + border: none; + width: 1%; + white-space: nowrap; + vertical-align: top; +} + +.posts-td-link { + border: none; + vertical-align:top; +} diff --git a/_site/blog/post-1/index/index.html b/_site/blog/post-1/index/index.html deleted file mode 100644 index 3c71fca..0000000 --- a/_site/blog/post-1/index/index.html +++ /dev/null @@ -1,42 +0,0 @@ -<!doctype html> -<html lang="en-us"> - <head> -<meta charset="utf-8"> - <title>Index</title> - <link rel="stylesheet" href="/assets/css/main.css"> - <link rel="stylesheet" href="/assets/css/normalize.css"> - <link rel="stylesheet" href="/assets/css/skeleton.css"> -</head> - - - <body> - - <div class="container"> - <ul id="navlist" class="left"> - - <li > - <a href="/">hme</a> - </li> - <li > - <a href="/projects/">proj</a> - </li> - <li > - <a href="/about/">abt</a> - </li> - <li><a href="/feed.xml">rss</a></li> - </ul> -</div> - - - - <main class="container" id="main"><p>An apple is a sweet, edible fruit produced by an apple tree.</p> - -<p>Apple trees are cultivated worldwide, and are the most widely grown -species in the genus Malus. The tree originated in Central Asia, where -its wild ancestor, Malus sieversii, is still found today. Apples have -been grown for thousands of years in Asia and Europe, and were brought -to North America by European colonists.</p> -</main> - - </body> -</html> diff --git a/_site/index.html b/_site/index.html index 21acaa8..9e75e34 100644 --- a/_site/index.html +++ b/_site/index.html @@ -29,19 +29,93 @@ - <main class="container" id="main"><ul> + <main class="container" id="main"><div class="articles"> + <table class="posts-table"> + + + <tr> + <td class="posts-td-link"> + <a href="/archive/neo4j-a-star-search/">Neo4J A* search</a> + </td> + <td class="posts-td-time"> + <span class="post-meta"> + <time datetime="2025-09-14 00:00:00 +0800">2025-09-14</time> + </span> + </td> + </tr> + - <li> - <h5><a href="/blog/post-1/index/">Index</a></h2> - <p>An apple is a sweet, edible fruit produced by an apple tree.</p> - </li> + <tr> + <td class="posts-td-link"> + <a href="/archive/my-first-pcb/">My first PCB</a> + </td> + <td class="posts-td-time"> + <span class="post-meta"> + <time datetime="2025-07-14 00:00:00 +0800">2025-07-14</time> + </span> + </td> + </tr> + + + + <tr> + <td class="posts-td-link"> + <a href="/archive/mosfet-switches/">MOSFETs</a> + </td> + <td class="posts-td-time"> + <span class="post-meta"> + <time datetime="2025-06-22 00:00:00 +0800">2025-06-22</time> + </span> + </td> + </tr> + + + + <tr> + <td class="posts-td-link"> + <a href="/archive/awesome-books/">Awesome books</a> + </td> + <td class="posts-td-time"> + <span class="post-meta"> + <time datetime="2025-04-20 00:00:00 +0800">2025-04-20</time> + </span> + </td> + </tr> + + + + <tr> + <td class="posts-td-link"> + <a href="/archive/arduino-uno/">Notes on programming ATmega328P chips</a> + </td> + <td class="posts-td-time"> + <span class="post-meta"> + <time datetime="2025-04-10 00:00:00 +0800">2025-04-10</time> + </span> + </td> + </tr> + -</ul> + <tr> + <td class="posts-td-link"> + <a href="/archive/arduino-due/">Bare-metal ARM Cortex M3 chips</a> + </td> + <td class="posts-td-time"> + <span class="post-meta"> + <time datetime="2024-10-05 00:00:00 +0800">2024-10-05</time> + </span> + </td> + </tr> + + + + </table> </div> + </main> </body> diff --git a/assets/css/main.css b/assets/css/main.css index fbc22f7..43afb69 100644 --- a/assets/css/main.css +++ b/assets/css/main.css @@ -217,3 +217,14 @@ and (min-device-width : 768px) { } } +.posts-td-time { + border: none; + width: 1%; + white-space: nowrap; + vertical-align: top; +} + +.posts-td-link { + border: none; + vertical-align:top; +} @@ -3,15 +3,25 @@ layout: default title: ASCIIMX --- -<ul> - {% assign docs = site.blog %} - {% assign latest = docs | sort: 'date' | reverse %} - {% for item in docs %} - <li> - <h5><a href="{{ item.url }}">{{ item.title }}</a></h2> - {{ item.excerpt }} - </li> +<div class="articles"> + <table class="posts-table"> + + {% assign posts = site.archive | sort: 'date' | reverse %} + {% for post in posts %} + + <tr> + <td class="posts-td-link"> + <a href="{{ post.url }}">{{ post.title }}</a> + </td> + <td class="posts-td-time"> + <span class="post-meta"> + <time datetime="{{ post.date }}">{{ post.date | date: "%Y-%m-%d" }}</time> + </span> + </td> + </tr> + {% endfor %} -</ul> + </table> </div> + |
