Project: Sudoku Solver in NASM

This project is a working copy.

Updates

2015-06-12
Read input board from STDIN
Print formatted input board

2015-06-19
Added function to check if a cell value has any duplicate within the same row
Fixed comments containing instructions to compile and run
Added comments

2015-06-27
Added function to check if a cell value has any duplicate within the same column
Fixed comments containing instructions to compile and run

2015-07-10
Added function to check if a cell value has any duplicate within the same miniboard

2015-07-24
Added function to check if a cell value is valid (no duplicate value within same row, column or miniboard)
Added function to get next highest valid value for a cell

2015-07-31
Implemented main search and backtrack solver logic
Added and modified comments
Fixed bug with func_check_value_row function
Added line break after printing board in func_print_board function

[gist https://gist.github.com/sharpbang-root/8f45fafcf50921d65195 /]
Advertisements

Automatic Time Synchronisation for D-Link ShareCenter DNS-320

If the current date/time for the D-Link ShareCenter DNS-320 gets reset everytime the the NAS shuts down, a script can be used to perform date/time synchronisation on boot-up. (This requires Fonz fun_plug to be installed.)

Create the file /ffp/start/timesync.sh with the following content.

#!/ffp/bin/sh

# PROVIDE: timesync
# REQUIRE: inetd

. /ffp/etc/ffp.subr

name="timesync"
start_cmd="timesync_start"

timesync_start()
{
    date +%s -s @`wget -O - -q http://www.icanhaztimestamp.com/`;
}

run_rc_command "$1"

Explanations

The key to the script lies in the following line.

date +%s -s @`wget -O - -q http://www.icanhaztimestamp.com/`;

It can be broken down as follows.

www.icanhaztimestamp.com

This is a web service that returns the current UNIX timestamp in plain text. (I.e. the HTTP response body contains nothing but the ten-digit current UNIX timestamp.)

wget -O - -q http://www.icanhaztimestamp.com/

This wget command makes a request to the specified URL and outputs the HTTP response body (in this case, the ten-digit current UNIX timestamp).

date +%s -s @`wget -O - -q http://www.icanhaztimestamp.com/`

This date command sets the current date/time to the specified UNIX timestamp which, in this case, is the response from www.icanhaztimestamp.com.

This script would run once when the NAS boots up, and hence, the date/time would be synchronised.

Note: wget had to be used to obtain the current date/time because ntpd did not appear to be present.

Note: Though the DNS-320 administrator console allowed an NTP server to be configured, the NAS did not appear to synchronise the time with the server. (Perhaps because ntpd was not present.)

References:

[1] https://nas-tweaks.net/tutorials/
[2] http://www.icanhaztimestamp.com/

Using Page Heap Verification to Locate Heap Allocation Bugs

The program code below has a heap overflow bug. The memory location referenced by lpHeapVar1 is allocated one byte, but the subsequent code attempts to fill it with ten bytes of data, thus overflowing it.

#include <stdlib.h>
#include <stdio.h>
#include <strings.h>

int main(int argc, char **argv) {
    char stackVar[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    char *lpHeapVar1, *lpHeapVar2;
    printf("before allocating heap 1\n");
    lpHeapVar1 = (char *) malloc(1);
    printf("after allocating heap 1\n");
    printf("before overflowing heap 1\n");
    memcpy(lpHeapVar1, &stackVar, 10); // heap overflow
    printf("after overflowing heap 1\n");
    // other code here
    printf("before allocating heap 2\n");
    lpHeapVar2 = (char *) malloc(1);
    printf("after allocating heap 2\n");
    return 0;
}

When the program code above is compiled and run, it will crash at the following line of code.

lpHeapVar2 = (char *) malloc(1);

However, there is nothing wrong with the second malloc call itself. This makes the bug difficult to track down, even if a heap overflow is suspected to be the cause, especially if many lines of code separate the point of overflow and the subsequent heap allocation.

Page heap verification can help to track down such bugs. GFlags (included with Debugging Tools for Windows) is used to enable page heap verification.

C:\> gflags.exe -p /enable heap_allocate.exe /full
path: SOFTWARE\Microsoft\Windows NT\CurrentVersion\Image File Execution Options
    heap_allocate.exe: page heap enabled

where heap_allocate.exe is the compiled executable file.

Subsequently, when the program is run, it will crash at the point of the heap overflow (the memcpy function call).

References

[1] https://msdn.microsoft.com/en-us/library/windows/hardware/ff549566%28v=vs.85%29.aspx

Adding Album Cover to a FLAC File

When converting a wave file to a FLAC file using the flac command, an album cover can also be added by using the –picture argument with an input image file.

$ flac -0 ... --picture="3|image/jpeg|||cover.jpg" ... filename.wav

where 3 means that the picture is a front cover, cover.jpg is the cover image file, and filename.wav is the name of the input wave file.

Alternatively, metaflac can be used to add an album cover to a FLAC file.

$ metaflac --import-picture-from="3|image/jpeg|||cover.jpg" filename.flac

where the format of the –import-picture-from argument follows the –picture argument of the flac command, and filename.flac is the name of the FLAC file to be processed.

Note: flac and metaflac may not be present in a default installation. It can be installed through the package manager.

References

[1] https://sharpbang.wordpress.com/2013/08/07/converting-a-wave-file-to-a-flac-file/
[2] http://linux.die.net/man/1/flac
[3] http://linux.die.net/man/1/metaflac
[4] https://www.xiph.org/vorbis/doc/v-comment.html

Configuring Dovecot and Postfix for Local Webmail Testing

Steps for configuring Dovecot and Postfix for locally testing a webmail deployment (e.g. Roundcube Webmail).

Configure Hostname

1. Change the machine hostname (e.g. mail.testmail.com).

# hostname mail.testmail.com

2. Add or change the following line in the /etc/hosts file to point the configured hostname (e.g. mail.testmail.com) to the loopback address.

127.0.0.1   localhost localhost.localdomain localhost4 localhost4.localdomain4 mail.testmail.com

Add Email User

3. Add and configure a user account for Dovecot IMAP access.

# useradd -m mailuser
# passwd mailuser # and enter a password for the new user
# mkdir /home/mailuser/Maildir
# chown mailuser:mailuser /home/mailuser/Maildir

Install Packages

4. Install the dovecot and postfix packages.

# yum install dovecot postfix

Configure Dovecot

5. Add the following lines in the /etc/pam.d/dovecot file for the Dovecot PAM configuration.

auth       required     pam_unix.so
account    required     pam_unix.so

6. Add or uncomment the following lines in the Dovecot configuration file /etc/dovecot/dovecot.conf.

protocols = imap pop3 lmtp
listen = *, ::
base_dir = /var/run/dovecot/

7. Uncomment and change the following line in the /etc/dovecot/conf.d/10-auth.conf file to allow plaintext authentication for testing purposes.

disable_plaintext_auth = no

8. Uncomment and change the following line in the /etc/dovecot/conf.d/10-mail.conf file to set the email storage location.

mail_location = maildir:~/Maildir

9. Uncomment the following lines in the /etc/dovecot/conf.d/10-master.conf file to configure the IMAP listening port.

service imap-login {
  inet_listener imap {
    port = 143
  }
  ...
}

10. Uncomment and change the following line in the /etc/dovecot/conf.d/15-lda.conf file to set the postmaster email address.

postmaster_address = postmaster@mail.testmail.com

11. Uncomment the following lines in the /etc/dovecot/conf.d/auth-system.conf.ext file to configure Dovecot to use PAM for authentication.

passdb {
  driver = pam
  ...
  args = dovecot
}

Configure Postfix

12. Uncomment the following line in the /etc/postfix/main.cf file to configure Postfix to use the previously set hostname.

inet_interfaces = $myhostname, localhost

13. Comment out the following line in the /etc/postfix/main.cf file.

#inet_interfaces = localhost

14. Add the following line in the /etc/postfix/main.cf file to configure Postfix to use Dovecot LDA for mail delivery.

mailbox_command = /usr/libexec/dovecot/dovecot-lda -f "$SENDER" -a "$RECIPIENT"

Start Dovecot and Postfix

15. Start Dovecot.

# /etc/init.d/dovecot start

16. Start Postfix.

# /etc/init.d/postfix start

Install Webmail

17. Install the webmail package (e.g. Roundcube Webmail).

Troubleshooting

18. For troubleshooting, error messages will be in the /var/log/maillog file.

References

[1] http://wiki2.dovecot.org/
[2] http://wiki2.dovecot.org/PasswordDatabase/PAM
[3] http://wiki2.dovecot.org/LDA/Postfix

Installing Rockbox on Sansa Clip+ for Non-ASCII Support

The Sansa Clip+ is a portable music player with expandable storage (microSD), support for FLAC and Ogg Vorbis, and decent sound quality.

However, although it can play music files with filenames that contain non-ASCII characters, having such filenames in custom playlists would not work. The player simply ignores those files in the playlist. Using the M3U8 playlist extension does not work either.

One way to overcome this would be to install the Rockbox firmware on the Sansa Clip+.

Download Files

1. Download the original firmware, bootloader and the Rockbox build from http://www.rockbox.org/wiki/SansaAMS/. (Look for those files corresponding to Clip+.)

2. Download the mkamsboot tool from http://download.rockbox.org/bootloader/sandisk-sansa/mkamsboot/.

Create Patched Firmware

3. Extract the downloaded original firmware (clppa.bin).

4. Patch the Rockbox bootloader (bootloader-clipplus.sansa) into the original firmware (clppa.bin).

$ ./mkamsboot clppa.bin bootloader-clipplus.sansa patched.bin

Copy Files into Music Player

5. Set the USB mode of the Sansa Clip+ to MSC (mass-storage device class).

6. Copy the patched firmware into the root directory of the Sansa Clip+ internal storage, renaming the file as clppa.bin.

$ cp patched.bin /media/0123-4567/clppa.bin

where /media/0123-4567 is the mount point for the Sansa Clip+ internal storage.

7. Extract the Rockbox build (which should just be the .rockbox directory) into the root directory of the Sansa Clip+ internal storage.

$ unzip rockbox-sansaclipplus.zip -d /media/0123-4567

where rockbox-sansaclipplus.zip is the downloaded Rockbox build, and /media/0123-4567 is the mount point for the Sansa Clip+ internal storage.

8. The firmware will be updated when the device is unmounted.

Install Additional Fonts for Unicode Support

9. Download the latest font pack from http://www.rockbox.org/download/byhand.cgi.

10. Extract the 14-Rockbox-Mix.fnt and 16-GNU-Unifont.fnt font files into the .rockbox/fonts directory of the Sansa Clip+ internal storage.

$ unzip rockbox-fonts-3.13.zip .rockbox/fonts/14-Rockbox-Mix.fnt .rockbox/fonts/16-GNU-Unifont.fnt -d /media/0123-4567

where rockbox-fonts-3.13.zip is the downloaded font pack, and /media/0123-4567 is the mount point for the Sansa Clip+ internal storage.

11. Change the Rockbox settings to use one of these two fonts.

Settings > Theme Settings > Font

References

[1] http://www.sandisk.com/products/music-video-players/clip-plus-mp3-player/
[2] http://forums.sandisk.com/t5/Sansa-Clip-Sansa-Clip/Playlist-for-Songs-With-Non-ASCII-Filename-Characters/td-p/299106
[3] http://en.wikipedia.org/wiki/M3U
[4] http://www.rockbox.org/wiki/SansaAMS/

Adding EXIF Data Through Command Line

It is also possible to add EXIF data to an image through the command line. exiftool is a command line perl utility for manipulating EXIF data.

Usage Examples

$ exiftool -list
Available tags:
  3DRenderingType A100DataOffset AAFManufacturerID ACoordOfBottomRightCorner
  ACoordOfTopRightCorner AEAperture AEBAutoCancel AEBBracketValue AEBSequence
  AEBSequenceAutoCancel AEBShotCount AEBXv AEExposureTime AEFlags AELButton
  ...
  ...
  ...

Print a (very long) list of EXIF tags that can be read or written using the tool.

$ exiftool filename.jpg
ExifTool Version Number         : 8.60
File Name                       : filename.jpg
Directory                       : .
File Size                       : 357 kB
File Modification Date/Time     : 2013:08:23 23:43:42+08:00
...

View all the EXIF tags for an image file (in this case, filename.jpg).

$ exiftool -Title="Photo Title" filename.jpg 
    1 image files updated

Add the title (“Photo Title“) to the image file filename.jpg.

$ exiftool -Description="This is a description of the photo." filename.jpg 
    1 image files updated

Add the description (“This is a description of the photo.“) to the image file filename.jpg.

$ exiftool -XPKeywords="First Tag;Second Tag" filename.jpg
    1 image files updated

Add the tags (“First Tag” and “Second Tag“) to the image file filename.jpg.

$ exiftool -GPSLatitude=13.37 -GPSLatitudeRef=N -GPSLongitude=1.337 -GPSLongitudeRef=E filename.jpg
    1 image files updated

Add geolocation information (latitude 13.37 degree north and longitude 1.337 degree east) to the image file filename.jpg.

$ exiftool -Title -Description -XPKeywords -GPSLatitude -GPSLatitudeRef -GPSLongitude -GPSLongitudeRef filename.jpg
Title                           : Photo Title
Description                     : This is a description of the photo.
XP Keywords                     : First Tag;Second Tag
GPS Latitude                    : 13 deg 22' 12.00" N
GPS Latitude Ref                : North
GPS Longitude                   : 1 deg 20' 13.20" E
GPS Longitude Ref               : East

View the previously added EXIF information (title, description, tags and geolocation) from the image file filename.jpg.

Note: libimage-exiftool-perl is the package that contains the exiftool utility, and may not be present in a default installation. It can be installed through the package manager.

References

[1] http://linux.die.net/man/1/exiftool
[2] http://www.wikipedia.org/wiki/Exchangeable_image_file_format

Adding EXIF Data Using PHP

A simple PHP script to add image description and geolocation EXIF data to an image. The script makes use of the PHP EXIF Library (PEL) by Isolesen, which can be obtained from http://lsolesen.github.io/pel/.

PHP Code

<?php
set_include_path('lsolesen-pel-9f52634' . PATH_SEPARATOR . get_include_path());
require_once('src/PelJpeg.php');

$pelJpeg = new PelJpeg('in_filename.jpg');

$pelExif = $pelJpeg->getExif();
if ($pelExif == null) {
    $pelExif = new PelExif();
    $pelJpeg->setExif($pelExif);
}

$pelTiff = $pelExif->getTiff();
if ($pelTiff == null) {
    $pelTiff = new PelTiff();
    $pelExif->setTiff($pelTiff);
}

$pelIfd0 = $pelTiff->getIfd();
if ($pelIfd0 == null) {
    $pelIfd0 = new PelIfd(PelIfd::IFD0);
    $pelTiff->setIfd($pelIfd0);
}

$pelIfd0->addEntry(new PelEntryAscii(
        PelTag::IMAGE_DESCRIPTION, 'This is the image description'));

$pelSubIfdGps = new PelIfd(PelIfd::GPS);
$pelIfd0->addSubIfd($pelSubIfdGps);

setGeolocation($pelSubIfdGps, 13.37, 1.337);

$pelJpeg->saveFile('out_filename.jpg');

function setGeolocation(
        $pelSubIfdGps, $latitudeDegreeDecimal, $longitudeDegreeDecimal) {
    $latitudeRef = ($latitudeDegreeDecimal >= 0) ? 'N' : 'S';
    $latitudeDegreeMinuteSecond
            = degreeDecimalToDegreeMinuteSecond(abs($latitudeDegreeDecimal));
    $longitudeRef= ($longitudeDegreeDecimal >= 0) ? 'E' : 'W';
    $longitudeDegreeMinuteSecond
            = degreeDecimalToDegreeMinuteSecond(abs($longitudeDegreeDecimal));

    $pelSubIfdGps->addEntry(new PelEntryAscii(
            PelTag::GPS_LATITUDE_REF, $latitudeRef));
    $pelSubIfdGps->addEntry(new PelEntryRational(
            PelTag::GPS_LATITUDE, 
            array($latitudeDegreeMinuteSecond['degree'], 1), 
            array($latitudeDegreeMinuteSecond['minute'], 1), 
            array(round($latitudeDegreeMinuteSecond['second'] * 1000), 1000)));
    $pelSubIfdGps->addEntry(new PelEntryAscii(
            PelTag::GPS_LONGITUDE_REF, $longitudeRef));
    $pelSubIfdGps->addEntry(new PelEntryRational(
            PelTag::GPS_LONGITUDE, 
            array($longitudeDegreeMinuteSecond['degree'], 1), 
            array($longitudeDegreeMinuteSecond['minute'], 1), 
            array(round($longitudeDegreeMinuteSecond['second'] * 1000), 1000)));
}

function degreeDecimalToDegreeMinuteSecond($degreeDecimal) {
    $degree = floor($degreeDecimal);
    $remainder = $degreeDecimal - $degree;
    $minute = floor($remainder * 60);
    $remainder = ($remainder * 60) - $minute;
    $second = $remainder * 60;
    return array('degree' => $degree, 'minute' => $minute, 'second' => $second);
}
?>

Explanations

set_include_path('lsolesen-pel-9f52634' . PATH_SEPARATOR . get_include_path());
require_once('src/PelJpeg.php');

Import the necessary code. For this script, only PelJpeg.php from the Isolesen PEL library is needed.

$pelJpeg = new PelJpeg('in_filename.jpg');

Load the image file to be editied, in this case, in_filename.jpg.

$pelExif = $pelJpeg->getExif();
if ($pelExif == null) {
    $pelExif = new PelExif();
    $pelJpeg->setExif($pelExif);
}

$pelTiff = $pelExif->getTiff();
if ($pelTiff == null) {
    $pelTiff = new PelTiff();
    $pelExif->setTiff($pelTiff);
}

$pelIfd0 = $pelTiff->getIfd();
if ($pelIfd0 == null) {
    $pelIfd0 = new PelIfd(PelIfd::IFD0);
    $pelTiff->setIfd($pelIfd0);
}

Get the EXIF and the root image file directory (IFD) from the image.

$pelIfd0->addEntry(new PelEntryAscii(
        PelTag::IMAGE_DESCRIPTION, 'This is the image description'));

Add the description (in this case, the description is “This is the image description“.)

$pelSubIfdGps = new PelIfd(PelIfd::GPS);
$pelIfd0->addSubIfd($pelSubIfdGps);

Add a sub-IFD for the geolocation data.

setGeolocation($pelSubIfdGps, 13.37, 1.337);

Set the geolocation data (in this case, with a latitude of 13.37 and a longitude of 1.337). The setGeolocation function is explained below.

$pelJpeg->saveFile('out_filename.jpg');

Save the image which contains the additional EXIF data. In this case, the image is saved to out_filename.jpg.

function setGeolocation(
        $pelSubIfdGps, $latitudeDegreeDecimal, $longitudeDegreeDecimal) {
    $latitudeRef = ($latitudeDegreeDecimal >= 0) ? 'N' : 'S';
    $latitudeDegreeMinuteSecond
            = degreeDecimalToDegreeMinuteSecond(abs($latitudeDegreeDecimal));
    $longitudeRef= ($longitudeDegreeDecimal >= 0) ? 'E' : 'W';
    $longitudeDegreeMinuteSecond
            = degreeDecimalToDegreeMinuteSecond(abs($longitudeDegreeDecimal));

    $pelSubIfdGps->addEntry(new PelEntryAscii(
            PelTag::GPS_LATITUDE_REF, $latitudeRef));
    $pelSubIfdGps->addEntry(new PelEntryRational(
            PelTag::GPS_LATITUDE, 
            array($latitudeDegreeMinuteSecond['degree'], 1), 
            array($latitudeDegreeMinuteSecond['minute'], 1), 
            array(round($latitudeDegreeMinuteSecond['second'] * 1000), 1000)));
    $pelSubIfdGps->addEntry(new PelEntryAscii(
            PelTag::GPS_LONGITUDE_REF, $longitudeRef));
    $pelSubIfdGps->addEntry(new PelEntryRational(
            PelTag::GPS_LONGITUDE, 
            array($longitudeDegreeMinuteSecond['degree'], 1), 
            array($longitudeDegreeMinuteSecond['minute'], 1), 
            array(round($longitudeDegreeMinuteSecond['second'] * 1000), 1000)));
}

The function for setting the geolocation data. This function is needed because the library uses the degree-minute-second format for the latitude and longitude values, so the input decimal values have to be converted beforehand. Also, the library uses positive latitude and longitude values with a direction reference (N or S for latitude, and E or W for longitude), instead of positive and negative values.

function degreeDecimalToDegreeMinuteSecond($degreeDecimal) {
    $degree = floor($degreeDecimal);
    $remainder = $degreeDecimal - $degree;
    $minute = floor($remainder * 60);
    $remainder = ($remainder * 60) - $minute;
    $second = $remainder * 60;
}

The function for converting a decimal degree value to the degree-minute-second format.

Note: php is needed to run the script, and it may not  be present in a default installation. It can be installed through the package manager.

References

[1] http://lsolesen.github.io/pel/
[2] http://www.wikipedia.org/wiki/Exchangeable_image_file_format