Solving the Knapsack Problem with recursion in Java

Source available on Github.

Wikipedia has detailed description on the Knapsack problem and pseudo code on solving it. However, while implementing it with Elixir, seems that using simple recursion yields cleaner code. This is not the fastest way to solve the problem, but just easy to understand.

Basically, three return points within the recursion:

• if no items, result is 0 and return
• pop the first item. if item weight is over the max limit, return recursion result of the remaining items
• return the max between (current item value + recursion result with the remaining item) or (just the recursion result with the remaining items only)

However, not only it is inefficient, recursion will cause stack overflow error in Java. See the last (disabled) test case. Use -Xss parameter to increase stack size and run it for fun.

Caffeine (Simplified)

 

Found my old Turbo Pascal book on the bookshelf. Just so happen I was searching for a Windows program to prevent screen lock and found the open source Caffeine also written in Pascal.

Forked the repository and fired up Lazarus. Revised the UI a bit. Now it starts as a tray icon and can be controlled by the right-click menu.

Source code and executable available on github.

The Sins of the Fathers

 

Heard someone mentioned about the author Lawrence Block and found the ebook The Sins of the Fathers available from the library.

Overall not bad. Kind of nostalgic reading about the 70s. Will definitely see if can find the whole series.

Here is a review from Bing Chat:

The Sins of the Fathers is a gripping and gritty introduction to Matthew Scudder, a former cop turned private eye who operates in the dark and dangerous streets of New York City. Scudder is hired by a wealthy father to investigate the murder of his estranged son and his girlfriend (Bing's mistake. This should have been "his estranged daughter and her roommate"), but soon discovers that the case is more complex and twisted than it seems. The book is a masterful blend of mystery, suspense, and character study, as Scudder delves into the lives and secrets of the victims and their families, while also confronting his own demons and flaws. The Sins of the Fathers is a classic of hard-boiled fiction that will keep you hooked until the end.

Self-hosted Wyze Cam v3 camera without internet access - Part 1

This is part 1 of the notes on how to self-host Wyze Cam v3, without internet access, as a RTSP camera. 

Here Part 1 will focus on preparing the network setup. Part 2 (TBC) will be on configuring the Wyze camera.

Background 

For testing purposes, I have a Home Assistant(HA) setup with several Zigbee devices running Zigbee2MQTT and Mosquitto.

To add NVR feature, I have since installed Frigate and added a Google TPU card for accelerating event detection. The IP cameras used are Wyze Cam v3 patched with custom firmware to output two RTSP streams (a lower resolution for preview and event detection, and a higher resolution for recording).

Here are some highlights of the original setup

• The ISP dual-band router supports 5GHz network
• The HA machine is setup in a separate room running openSUSE Tumbleweed. It is connected to an Access Point (AP) via LAN cable
• The AP is an old dual-bank router flashed with DD-WRT custom firmware. It serves two purposes: the 5GHz network is configured as a wireless bridge to provide internet access to the HA machine and allow other devices on the home network to access HA, while the 2.4GHz network (with a different SSID) is configured as access point for IP cameras

The setup runs fine with one issue: the IP cameras have internet access. I don't like the idea that the IP cameras can "phone home" anytime. Ideally, after initial setup, I would like to remove the Internet access from those cameras.

Tried to setup virtual networks, bridges, and firewall rules etc on the AP. But none worked reliably.

So here is the new idea:

• since I have several USB wifi adapters not in use, I could add one to the HA machine and configure it as an AP with a different SSID and subnet. It will be running in 2.4GHz to minimize interference with the 5GHz home network
• with the HA being a Linux machine, I will have the flexibility on routing (or not routing) traffic around i.e. effectively blocking internet access for the cameras
• I don't need to access the IP cameras remotely (i.e. when away from home), don't need to receive any notifications on my phone, and don't mind giving up using the Wyze app. If I really need to access the cameras remotely, I could VPN back to my home network first.

A few things needed to be configured on the HA Linux machine.

EDIT 2024-06-02 A few changes on the device setup:

• the rtl8812au package from OpenSUSE isn't stable and keeping up to date with kernel updates. So ended up installing the driver from source as dkms
• using NetworkManager to setup host access point seems to cause conflicts on many things. Ended up to unmanage the wifi adapter with nm (adding "unmanaged-devices=interface-name:wlp0s16f0u1;" in /etc/NetworkManager/conf.d/99-localhost.conf). Then force the ip on the device with ifconfig with a custom systemd service. Finally use hostapd for the access point setup

EDIT 2024-06-10 script for the custom systemd service, assuming the interface is wlan0:

[Unit]
Description=Assign IP address to wifi interface for AP
Requires=sys-subsystem-net-devices-wlan0.device

Before=hostapd.service dnsmasq.service
After=sys-subsystem-net-devices-wlan0.device

[Service]
Type=oneshot
ExecStart=/usr/bin/ifconfig wlan0 up 192.168.20.1 netmask 255.255.255.0

[Install]
WantedBy=multi-user.target

USB wifi adapter

The wifi adapter I will be using has the Realtek 8812 chipset. The driver can be installed via `rtl8812au` package. However, installing it caused the Coral TPU dkms driver stopped working. Eventually, needed to install the newer version and recompile.

Next is to configure the wifi adapter as AP. Since the openSUSE machine is using NetworkManager, I used `nmcli` to configure it. The steps are similar to those mentioned here for Centos.

EDIT 2023-11-18. Some addition useful commands:

- disable WPA: sudo nmcli con modify "connection name" 802-11-wireless-security.proto rsn

- disable WPS: sudo nmcli con modify "connection name" 802-11-wireless-security.wps-method 1

EDIT 2023-11-25. To disable the excessive logging of the driver, change the log level to none

For the examples below, assume the new wifi interface is "wlan0" and has the IP address of 192.168.20.1/255.255.255.0. The two IP cameras will be assigned with address 192.168.20.91 and 192.168.20.92.

DHCP setup

Each IP camera will be assigned the same IP address via DHCP service provided by dnsmasq. Following these steps for a minimal setup.

local-service

conf-file=/etc/dnsmasq.d/trust-anchors.conf

dnssec

# only serve dhcp on the wifi interface

interface=wlan0

# some dynamic ip in case needed to connect for troubleshooting

dhcp-range=192.168.20.80,192.168.20.89,255.255.255.0,6h

# fixed ip for the ip cam

dhcp-host=d0:3f:27:xx:yy:zz,192.168.20.91

dhcp-host=d0:3f:27:aa:bb:cc,192.168.20.92

# announce the HA machine (192.168.20.1 here as an example) as DNS server and ntp server

dhcp-option=6,192.168.20.1

dhcp-option=option:ntp-server,192.168.20.1

conf-dir=/etc/dnsmasq.d/,*.conf

DNS setup

The dnsmasq will also be serving as DNS server for the cameras. To avoid them to keep querying the hard-coded NTP severs, create a conf file under /etc/dnsmasq.d directory to redirect them to local machine.

address=/time-a.inst.gov/192.168.20.1

address=/time-b.inst.gov/192.168.20.1

address=/time-a-g.inst.gov/192.168.20.1

address=/time-b-g.inst.gov/192.168.20.1

address=/clock.fmt.he.net/192.168.20.1

address=/ntp0.cornell.edu/192.168.20.1

NTPD time server

I like to configure the IP camera to overlay timestamp on the video. Unfortunately the Wyze camera firmware contains a binary that only query several hard-coded NTP servers. But the wz_mini_hacks firmware actually comes with a NTP process to update the time. More on how to set it up in part 2.

For now, make sure the HA machine has NTPD setup properly and ready. Run `sudo ntpq -c lpeer` to check

IP Masquerading

During the initial setup, the Wyze camera needs internet access. To allow the traffic routed to internet and back using NetworkManager and firewalld:

# assuming wlan0 is the device id of the wifi adapter configured with nmcli

sudo nmcli con up wlan0

# move the interface to trusted zone to allow all traffic

sudo firewall-cmd --zone=trusted --change-interface=wlan0

sudo firewall-cmd --zone=trusted --add-masquerade

# assuming eth0 is the LAN interface with internet access

sudo firewall-cmd --direct --add-rule ipv4 nat POSTROUTING 0 -o eth0 -j MASQUERADE

sudo firewall-cmd --direct --add-rule ipv4 filter FORWARD 0 -i wlan0 -o eth0 -j ACCEPT

sudo firewall-cmd --direct --add-rule ipv4 filter FORWARD 0 -i eth0 -o wlan0 -m state --state RELATED,ESTABLISHED -j ACCEPT

When we are done configuring IP cameras and making sure Frigate can access them, revoke the access and isolate the cameras from internet.

sudo firewall-cmd --direct --remove-rule ipv4 nat POSTROUTING 0 -o eth0 -j MASQUERADE

sudo firewall-cmd --direct --remove-rule ipv4 filter FORWARD 0 -i wlan0 -o eth0 -j ACCEPT

sudo firewall-cmd --direct --remove-rule ipv4 filter FORWARD 0 -i eth0 -o wlan0 -m state --state RELATED,ESTABLISHED -j ACCEPT

sudo firewall-cmd --zone=trusted --remove-masquerade

For a proper setup, should probably also move the wifi adapter to another zone. But well...

That is it for the Linux machine setup. Next part of the notes will focus on setting up the Wyze camera for self-hosting.

Coral USB Accelerator

 

Finally arrived after placing the order over a year ago. But I have since then ordered the mini pcie version and installed it on the Home Assistant machine for the Frigate NVR.

Now need to figure out what to do with this USB accelerator.

Microsoft Edge not redenering anything

 

Encounter issues with Microsoft Edge a few days ago on OpenSUSE Tumbleweed running on Ryzen APU. All contents are rendered as background color.

Starting it from command line shows the "Skia shader compilation error" and is a know bug affecting chromium.

Running it with "--disable-gpu-driver-bug-workarounds" can resolve it. Or, just delete the folder "~/.config/microsoft-edge/Default/GPUCache".

The Bullet That Missed

 

Third book in the series. The plot is definitely more complicated and more characters introduced. 4 out of 5.

Summary generated by ChatGPT:

"The Bullet That Missed" is the third book in the Thursday Murder Club series by Richard Osman. The book follows the Thursday Murder Club as they investigate a decade-old cold case that leads them to a local news legend and a murder with no body and no answers. Elizabeth, a member of the Thursday Murder Club, is visited by a new foe with a mission to kill or be killed. The book is about 400 pages long and has received positive reviews from critics and readers alike.

Trying out generative AI

 

(image generated with Bing)

Notes on trying out generative AI.

Google has a free online learning path on generative AI. Finished first few activities. Nothing technical and just high level concepts.

---

Has been trying to run the Facebook's LLaMA models locally. There is a project llama.cpp to run the models with c/c++ program. Support both CPU and GPU acceleration. So far only tried the 7B and 13B models. Not impressed. Should give the 65B model a try. But even with quantization, it will need almost 40GB just for loading the model. Will need to get more RAM first.

BTW, to download the LLaMA models, just google "download llama". There is a shell script to help to pull the files quickly

---

There is a new open source generative Falcon that clams to be better than LLaMA (at least for now).

The Man Who Died Twice

 

Quick read during the weekend. Second book for the series. Same plot feels old. And it seems a bit overstretch for a handful of people to take down the mafia boss, the MI5, and a local cartel at the same time. 2.5 out of 5.

Auto-generated summary:

The book “The Man Who Died Twice” is set in a retirement village and combines narrative tension and a fast-paced, complex plot with humor and naturalistic dialog. Although its tone is witty, the text addresses serious themes such as aging, mortality, friendship, and revenge. The story is told through dual narratives. Chapters alternate between the first-person diary entries of Joyce and a third-person narration covering multiple viewpoints.

Beasts and Beauty

 

Beasts and Beauty: Dangerous Tales. a quick read for a long weekend. Recommended.

A generated review:

"Beasts and Beauty: Dangerous Tales" by Soman Chainani is a delightfully wicked and humorous collection of stories that will keep readers hooked from start to finish. With his signature blend of fantasy and wit, Chainani takes classic fairy tales and gives them a dark twist, adding unexpected layers and surprises. The characters are richly developed, each with their own quirks and flaws, and the author's clever writing style adds an extra dose of charm. From mischievous beasts to cunning beauties, this book is a wild ride through a world where nothing is as it seems. Prepare to be enchanted and entertained!

Using Google Coral TPU on OpenSUSE

Installing the TPU driver

The official guide only covers steps for Debian. Third-party compiled binaries are available for Fedora, RHEL, and OpenSUSE etc. The RPM for OpenSUSE Tumbleweed can be downloaded directly here. 

Once downloaded, install the RPM file with "sudo zypper install gasket..."

Seems OpenSUSE now has the gasket driver in repository. Just install it with "sudo zypper install gasket-driver gasket-driver-kmp-default"

EDIT 20240524: seems that the gasket driver is removed from the OpenSUSE repository. So I guess back to manual installation with RPM.

Installing the userspace runtime driver

The userspace driver can be built from source inside docker:

git clone https://github.com/google-coral/libedgetpu.git

cd libedgetpu

CPU=k8 DOCKER_CPUS="k8" DOCKER_IMAGE="ubuntu:18.04" DOCKER_TARGETS=libedgetpu make docker-build

Copy the files from "out" folder and install using ldconfig:

sudo mkdir -p /usr/lib/tpu/lib

sudo cp --preserve=links out/direct/k8/* /usr/lib/tpu/lib

echo /usr/lib/tpu/lib | sudo tee -a /etc/ld.so.conf.d/tpu.conf

sudo ldconfig

Grant permission

Running the Python examples may fail with error "failed to load delegate...". This is due to permission issue. Add your user to the group "apex" with the command "sudo usermod -aG apex [your username]".

Also, if using the USB accelerator instead, add two rules to the udev file "/etc/udev/rules.d/65-apex.rules" and reboot:

SUBSYSTEM=="usb",ATTRS{idVendor}=="1a6e",GROUP="apex"

SUBSYSTEM=="usb",ATTRS{idVendor}=="18d1",GROUP="apex"

Running the examples

If you followed the above steps to install drivers, you may need to reboot before running any example.

The "pycoral" package mentioned on the officail guide is kind of confusing. The "pycoral" from pypi is actually a totally unrelated package. What we need for the TPU can be found here.

Also, there is no support for Python 3.10 yet. So needed to use 3.9. To install packages in order to run the example:

python3.9 -m venv venv

. venv/bin/activate

pip install numpy pillow

python -m pip install --extra-index-url https://google-coral.github.io/py-repo/ pycoral~=2.0

Then follow the steps on the official guide to run the example.

$ python3 examples/classify_image.py --model test_data/mobilenet_v2_1.0_224_inat_bird_quant_edgetpu.tflite --labels test_data/inat_bird_labels.txt --input test_data/parrot.jpg
----INFERENCE TIME----
Note: The first inference on Edge TPU is slow because it includes loading the model into Edge TPU memory.
12.8ms
2.8ms
2.8ms
2.8ms
2.8ms
-------RESULTS--------
Ara macao (Scarlet Macaw): 0.75781

All Systems Red

Got notification from public library that my hold on All Systems Red is ready. Finished it in one sitting after dinner.

Good short read. I guess i will have to pickup the whole series.

The following is an auto-generated summary:

All Systems Red is a science fiction novella by Martha Wells, published in 2017. It is the first book in The Murderbot Diaries series, which follows the adventures of a self-aware security robot that calls itself Murderbot. Here is a brief summary of the book:

Murderbot is assigned to protect a team of scientists who are surveying a planet for its natural resources. However, it has secretly hacked its governor module, which allows it to act independently and watch soap operas. When one of the scientists is attacked by a giant creature that was not in their data, Murderbot saves her and reveals some of its human traits. The team leader, Dr. Mensah, asks Murderbot to help them investigate why their information is incomplete and corrupted.

Murderbot discovers that another survey team on the other side of the planet has been killed by rogue security robots, and that someone is trying to sabotage their mission and eliminate them. Murderbot and the scientists have to escape from their habitat and fight off the attackers, while also dealing with their mixed feelings about Murderbot’s autonomy and past. Along the way, Murderbot learns more about itself and its emotions, and develops a bond with the humans it protects.

Changing the backup approach

Here is my current backup strategy. Basically all devices backup to a NAS (which also hosts shared files). And periodically, backup the whole NAS to an offline PC:

The "backup of backup" setup has a few downsides:

• The work of digging out and connecting the old PC to the network periodically. Additional hardware / software maintenance.
• The software RAID 5 needs multiple HDDs, usually retired hardware previously used in the NAS. High risk of failure.

An alternative would be using external USB HDDs for the "backup of backup":

First attempt:

• Use external HDDs via USB/eSATA for the "backup of backup". Rotate between two external HDDs to minimize the chance of single point of failure
• Use veracrypt to encrypt the whole external HDD device
• Within the encrypted volume, use BTRFS and mount with compression. Can also use the snapshot function of BTRFS if necessary
• Sadly the NAS is running a very old version of Synology software and it doesn't support veracrypt or BTRFS. Will need to do this on a desktop PC.

While BTRFS do compression and snapshots, will need to pay attention on the disk usage. It is inefficient and difficult to re-balance if the free space is low (the main reason why I gave up on using BTRFS on boot partition even when it is the default for OpenSUSE). Should probably do a re-balance after every rsync.

Preliminary results:

• Only less than 1/10th of the files are actually compressed. Probably because the NAS manly stores photos, movies, and backup archives... in which already in compressed format.

~$ sudo compsize /mnt/backup
Processed 117244 files, 1223867 regular extents (1223867 refs), 17472 inline.
Type       Perc     Disk Usage   Uncompressed Referenced   
TOTAL       95%      1.5T         1.6T         1.6T        
none       100%      1.5T         1.5T         1.5T        
zstd        22%       22G         103G         103G

• Encounter RAID read errors and veracrypt issues. May need to think about doing checksum after backup

ata7.00: exception Emask 0x0 SAct 0xff800c SErr 0x0 action 0x0

ata7.00: irq_stat 0x40000008

ata7.00: failed command: READ FPDMA QUEUED

ata7.00: cmd 60/08:78:88:92:ed/00:00:73:00:00/40 tag 15 ncq dma 4096 in

                                    res 51/40:01:8f:92:ed/00:00:73:00:00/40 Emask 0x409 (media error) <F>

ata7.00: status: { DRDY ERR }

ata7.00: error: { UNC }

ata7.00: ATA Identify Device Log not supported

ata7.00: ATA Identify Device Log not supported

ata7.00: configured for UDMA/133

sd 6:0:0:0: [sde] tag#15 FAILED Result: hostbyte=DID_OK driverbyte=DRIVER_OK cmd_age=3s

sd 6:0:0:0: [sde] tag#15 Sense Key : Medium Error [current] 

sd 6:0:0:0: [sde] tag#15 Add. Sense: Unrecovered read error - auto reallocate failed

sd 6:0:0:0: [sde] tag#15 CDB: Read(10) 28 00 73 ed 92 88 00 00 08 00

blk_update_request: I/O error, dev sde, sector 1944949391 op 0x0:(READ) flags 0x4000 phys_seg 1 prio class 0

ata7: EH complete

md/raid:md0: read error corrected (8 sectors at 1944947336 on sde1)

To be continued...

Some useful commands, assuming sdd is the external HDD:

# create veracrypt volume

sudo veracrypt --volume-type=normal -c /dev/sdd

# mount veracrypt volume
sudo veracrypt --filesystem=none --slot=1 /dev/sdd

# create BTRFS
sudo mkfs.btrfs -L backup /dev/mapper/veracrypt1

# mount BTRFS with compression
sudo mount -o compress=zstd:15 /dev/mapper/veracrypt1 /mnt/backup

# check BTRFS compression ratio
sudo compsize /mnt/backup

References:

https://wiki.archlinux.org/title/VeraCrypt

https://man.archlinux.org/man/btrfs.5#COMPRESSION

Load testing APIs with Grafana k6

 Trying out Grafana k6 for performance testing. Heard that it is way better than Apache JMeter.

 

Setup

Using k6 with docker is easy. Just pull the image and run whatever test script we have prepared, e.g.:

docker run --rm -i grafana/k6 run - <script.js

And it should output the result similar to this when done:

But I wanted to store the the output and visualize the result, like the screenshot at the top of this post. Especially I wanted to see the impact when increasing number of concurrent access. Hence I have decided to run k6 with timescaledb and Grafana.

Luckily, there is also a docker solution for that. The only changes I have done was modifying docker-compose.yml to mount the database data directory with host folder for easy clean up:

Otherwise, just build the special k6 image that supports timescaledb and start the containers:

docker-compose build k6

docker-compose up -d

Note that the actual k6 container to run the script won't be started by docker-compose. Instead it will be executed separately, e.g. with a shell script:

#!/bin/sh
set -e

TAG_BASE="newssum"
TAG_NAME="$TAG_BASE-$(date +%s)"

docker run --rm --net=host -e K6_OUT=timescaledb=postgresql://k6:k6@localhost:5432/k6 -i xk6-output-timescaledb-k6 run --tag testid=$TAG_NAME - < k6/newssum.js

Test script

I have decided to try out load testing my newssum APIs. The script itself is fairly straightforward. A few points to note:

• the test will be ramping up the number of virtual users (VUs) slowly from 20 to 160 to show the impact on heavy loading
  

• since the newssum APIs cache the result, the script will call them once during the setup stage to preload them
• by default, k6 uses a separate VU to execute the setup (only once, before the actual test start). Hence each VU will need to find out the available "sources" itself in the "default" function when running the actual load test
  

 

 Once the execution is done, result can be visualized with Grafana container by pointing the browser to http://localhost:3000. e.g.:

 

For this specific example, can see that newssum starts to struggle once we have over ~100 concurrent requests as the 95th percentile shoots up.

tl;dr

I can see why developers like k6 over JMeter. It is simple and straightforward to use Javascript to create load tests that require special setup.