
If you've never heard of the MiniDisc don't worry, you're not alone.

If you're curious, you can catch up by reading the [Wikipedia page](https://en.wikipedia.org/wiki/MiniDisc),
or the old community portal [minidisc.org](http://www.minidisc.org/), or interact with the reddit community of [/r/minidisc](https://reddit.com/r/minidisc).

If you're not, long story short, it's a dead music format released by Sony at the beginning of the '90s, that was slowly killed
by the popularity of the many MP3 players that started coming out in the early 2000s.

Some of the last MiniDisc players, branded as _NetMD_ units, were equipped with a USB port that allowed for recording music onto the device by using the infamously SonicStage software (Windows only, of course).
When Sony abandoned the MiniDisc, that software was left unmaintained and, nowadays, it can't run outside virtual machines or without using dangerously unsigned drivers.

Luckily the OSS community managed to completely reverse engineer the NetMD protocol and, before the death of the MiniDisc, the [linux-minidisc](https://wiki.physik.fu-berlin.de/linux-minidisc/doku.php) project was released.

A few of weeks ago, just before the infamously Coronavirus lockdown here in Italy, I've been lucky enough to find my old [MZ-N710](https://www.minidisc.org/part_Sony_MZ-N710.html) in my parents' basement.
Determined to make it work on my Macbook, I brought it home and successfully managed to compile and run the linux-minidisc CLI.

## Porting the MiniDisc to Web

The process for uploading the music via the CLI was comprised of 2 steps:

1. Convert your music

- Use `ffmpeg` <sup>[[1]](#ffmpeg)</sup> to create a 16bit 44100Hz pcm wav file (SP quality)
- Use `atrac3denc` <sup>[[2]](#atracdenc)</sup> to create a 132/66 Kbit ATRAC3 file (LP2/LP4 quality)

2. Use the CLI to send the converted music to the device

Not the most _user friendly_ process for those who're not fancy to type commands in a terminal.

So, after pondering for a while, I realized these steps could have been encapsulated in a _no-install-required_
progressive web app, for a considerable step up in the ease of the process.

I would just use:

- **WebUSB**<sup>[[8]](#webusb)</sup> to replace the CLI for communicating with the NetMD device
- **emscripten**<sup>[[9]](#emscripten)</sup> to bring `ffmpeg` and `atracdenc` into the browser
- **React**<sup>[[10]](#reacjs)</sup> to create a simple UI

### 1. Writing a library

I started by porting the code from linux-minidisc to a new JS library that I've now published on npm, called `netmd-js`<sup>[[3]](#netmdjs)</sup>.

This library implements the NetMD protocol and takes care of the USB communication with the device.
It will also allow other devs to write their own app, should mine not suit their needs.

It runs either in `nodejs` and in every browser supporting the WebUSB standard, and uses _Worker Threads_<sup>[[4]](#workerthreads)</sup> or
_Web Workers_<sup>[[5]](#webworkers)</sup> to speed up the
music encryption step required by the protocol. The encryption has been implemented on top of _CryptoJS_<sup>[[6]](#cryptojs)</sup>.

### 2. Using emscripten

I was lucky enough to find a project called `ffmpeg.js`<sup>[[7]](#ffmpegjs)</sup> that already ported ffmpeg to WASM.
So, the only thing left to do was to configure it properly and recompile, just to trim down the binary size.
A full tutorial is available in the GitHub page of `ffmpeg.js`.

Then, I've followed a similar process to cross compile the `atracdenc` encoder and eventually write a simple JS wrapper around it.

### 3. The Web MiniDisc Application

After gathering all the bricks together, I've shifted my focus to design the app's user interface and experience.

<div class="mtop-1-m mtop-1-d line-21-d" style="text-align: center;">
    <img src="/images/webminidiscapp.png" alt="Web MiniDisc App Wireframe" style="width: 100%;"/>
</div>

> _A dead simple user experience_

Then I started off with the classic _create react app + TypeScript_ template, and added _redux_ and _material-ui_ components... a _no-frills_ setup.

## How to use a NetMD device in 2020

A couple of nights later I was ready to record the first demo of the the Web MiniDisc Application.

It has been exciting to see the app work seamlessly both on my Macbook and on my Android phone without an `if` needed.

<iframe class="line-17-d line-11-m" src="//www.youtube.com/embed/Frs8qhw0g9Y" frameborder="0" allowfullscreen></iframe>

### Public launch

Honestly, there aren't many places to launch a MiniDisc app in 2020 :)<br/>
It's a pretty tiny niche.

However, I have been lurking for some time in [/r/minidisc](https://www.reddit.com/r/minidisc/) and decided to start from there.
[The feedback was great](https://www.reddit.com/r/minidisc/comments/fn4acd/web_minidisc_application/), and people even responded with a few bug reports and feature requests.

### Links

If you're a lucky owner of a NetMD device, you can try the app yourself at

<a href="https://stefano.brilli.me/webminidisc/" target="_blank">https://stefano.brilli.me/webminidisc/</a>

Or, if you just want to browse the code, everything's available on GitHub.

<a href="https://github.com/cybercase/webminidisc" target="_blank">https://github.com/cybercase/webminidisc</a>

### References

1. FFmpeg, <a href="https://ffmpeg.org/" target="_blank" id="ffmpeg">https://ffmpeg.org/</a>
2. atracdenc, <a href="https://github.com/dcherednik/atracdenc" target="_blank" id="atracdenc">https://github.com/dcherednik/atracdenc</a>
3. netmd-js, <a href="https://github.com/cybercase/netmd-js" target="_blank" id="netmdjs">https://github.com/cybercase/netmd-js</a>
4. Worker Threads, <a href="https://nodejs.org/api/worker_threads.html" target="_blank" id="workerthreads">https://nodejs.org/api/worker_threads.html</a>
5. Web Workers, <a href="https://developer.mozilla.org/en-US/docs/Web/API/Web_Workers_API/Using_web_workers" target="_blank" id="webworkers">https://developer.mozilla.org/en-US/docs/Web/API/Web_Workers_API/Using_web_workers</a>
6. CryptoJS, <a href="https://code.google.com/archive/p/crypto-js/" target="_blank" id="cryptojs">https://code.google.com/archive/p/crypto-js/</a>
7. ffmpeg.js, <a href="https://github.com/ffmpegjs/ffmpeg.js" target="_blank" id="ffmpegjs">https://github.com/ffmpegjs/ffmpeg.js</a>
8. WebUSB, <a href="https://wicg.github.io/webusb/" target="_blank" id="webusb">https://wicg.github.io/webusb/</a>
9. emscripten, <a href="https://emscripten.org/" target="_blank" id="emscripten">https://emscripten.org/</a>
10. React, <a href="https://reactjs.org/" target="_blank" id="reacjs">https://reactjs.org/</a>

_-- 26/03/2020_


Bringing back to life the MiniDisc with WebUSB and WASM

The Web MiniDisc App

Get control of your MiniDisc device thanks to WebUSB and WASM

The Web MiniDisc Application - Use your old NetMD device in the browser


I'm happy to announce my first macOS Application:<br/>
**Mutant: a GraphQL Explorer App for macOS**

**UPDATE: I've abandoned this project and is currently unmaintained.**

It's a handy tool for GraphQL developers used to jump between
[Graph*i*QL](https://github.com/graphql/graphiql) and
[GraphQL-Voyager](https://github.com/APIs-guru/graphql-voyager).
Mutant combines the features of these two great tools in a lightweight macOS app.

~~There's still a lot of work to do, so I'm running a **beta test** to gather some feedback, and if you are a
GraphQL developer I can't wait to hear from you.~~

~~You can [download here](https://mutant.ams3.digitaloceanspaces.com/Mutant%201.0.0-beta.3.zip) the latest version of the app
and drop your thoughts to [stefano@brilli.me](mailto:stefano@brilli.me).~~

- _5 Jan 2018: Released 1.0.0-beta.3_</br>
  Removed reference to outdated swift dylib.

### Zoom and Pan over your GraphQL Schema with Mutant

<iframe class="line-11-m line-17-d" src="https://www.youtube.com/embed/zDZAHtU3GrM" frameborder="0" gesture="media" allow="encrypted-media" allowfullscreen></iframe>

### Compose your GraphQL Query with Autocompletion and Assistant

<iframe class="line-11-m line-17-d" src="https://www.youtube.com/embed/ei5ev-9kKKU" frameborder="0" gesture="media" allow="encrypted-media" allowfullscreen></iframe>

_-- 21/12/2017_


a GraphQL Explorer App for macOS

Mutant - a GraphQL Explorer App for macOS


Current DOM specification provides 2 event types for handling keyboard actions<sup>[[1]](#keypress)</sup>:

- `keydown`
- `keyup`

These events match the physical actions of pressing and releasing a key of the keyboard, and have a payload with the
result of _keymapping_<sup>[[2]](#keymapping)</sup> by the OS (or any software in between), taking into account current _layout_, modifier and dead keys.

The result of _keymapping_ is stored in the `key` property of the event according to the _key algorithm_<sup>[[3]](#keyproperty)</sup>.
The pressing of a specific key can be caught just by listening for `keydown` and checking the `key` prop. e.g.

    let shortcutHandler = (event) => {
        // Shortcut: l
        if (event.key === 'l') {
            // Simplest case; Facebook use the same shortcut to like items in the feed.
            console.log('"l" is pressed')
        }
    }

    document.addEventListener('keydown', shortcutHandler)

## Modifiers

Keyboard shortcuts may require the combination of a character key and one or more modifiers<sup>[[4]](#modifier)</sup>.
Modifiers like `Meta` or `Ctrl` usually don't have the purpose of altering the unicode produced by a key,
so it's easy to define and catch a shortcut combination using the modifiers props stored in the event payload. e.g.

    let shortcutHandler = (event) => {
        // Shortcut: Meta+c
        if (event.key === 'c' && event.metaKey === true) {
            // The famous "Copy" shortcut on macOS
            console.log('"Meta+c" pressed')
        }
    }

On the other hand `Alt` and `Shift` modifiers may alter the unicode produced by a key, leading to issues in shortcut definition and catching. e.g.

    let shortcutHandler = (event) => {
        // Shortcut: Meta+Shift+s
        if (event.key === 's' && event.metaKey === true && event.shiftKey) {
            // The "Save All" shortcut
            console.log('"Meta+Shift+s" pressed')

            // WARNING
            // This won't work becase the "Shift" modifier change the unicode
            // of "S" key from "s" (lowercase) to "S" (uppercase)
        }
    }

## Normalization

Fixing the previous example is trivial: just replace the lowercase "s" with the uppercase "S" in the shortcut definition.
The new definition considers the effect produced from the `Shift` modifier, making the code work just fine. e.g.

    let shortcutHandler = (event) => {
        // Shortcut: Meta+Shift+S
        if (event.key === 'S' && event.metaKey === true && event.shiftKey) {
            // The Normalized "Save All" shortcut
            console.log('"Meta+Shift+S" pressed')

            // This works as expected
        }
    }

Let's call **Normalization** the action of replacing of the
character key in a keyboard shortcut, with the unicode produced from the same character key plus the modifiers in the shortcut.

## Layouts

Normalization falls short when considering multiple layouts; in fact it's layout dependant. e.g.:

- Normalization<sub>US</sub> for `Meta + Shift + 2` is `Meta + Shift + @`
- Normalization<sub>IT</sub> for `Meta + Shift + 2` is `Meta + Shift + "`
- Normalization<sub>FR</sub> for `Meta + Shift + 2` is `Meta + Shift + 2`.

This limits the Normalization effectiveness to just the shortcuts that use a character key for which its modified unicode char, according to the shortcut modifiers, is the same across every layout.
Let's call these shortcuts _layout-safe_. e.g.:

- Any lowercase [a-z] letter plus the `Shift` modifier should produce the uppercase version of that letter in every layout.

## Recap

When definining shortcuts for the browsers and multiple layouts it's worth considering that:

- Browsers and OS catch shortcuts too; be aware of collisions.
- Browsers don't provide an API for knowing the current layout.
- Some key may not be available on some layouts or may require additional modifiers to produce the same character.
- If the shortcut contains a character key, modifiers may change the unicode emitted by the `keydown` in an unpredictable way.

## Workaround Ideas

### Catch 'Em All

Given a shortcut, the idea is to collect its Normalization for every layout and listening for all of them.

    let shortcutHandler = (event) => {
        if ((event.key === '2' && event.metaKey === true && event.shiftKey) ||
            (event.key === '"' && event.metaKey === true && event.shiftKey) ||
            (event.key === '@' && event.metaKey === true && event.shiftKey)) {
            // This catches the "Meta+Shift+2" on US, IT, and FR layouts
            console.log('"Meta+Shift+2" pressed')
        }
    }

The obvious problem is that every shortcut ends up producing a set of Normalized shortcuts, and if the interesection of these sets is not empty it's impossible to choose which shortcut was triggered. e.g.

1. Normalization<sub>[US, IT]</sub> for `Meta+Shift+=` is [`Meta+Shift++`, `Meta+Shift+*`]
2. Normalization<sub>[US, IT]</sub> for `Meta+Shift+8` is [`Meta+Shift+*`, `Meta+Shift+(`]

Clearly `Meta+Shift+*` falls into the intersection, making impossible to know if the source is `Meta+Shift+=` on IT layout or `Meta+Shift+8` on US layout.

### Just Ask

The application can infere the keyboard layout using language and location of the browser. Then the Normalization function for such layout is used for catching shortcuts unambiguosly.

### Recovering Numbers

Shortcuts with number keys plus modifiers are not _layout-safe_.
However, the number keys position on the physical layout should be the same for most of Latin script layouts [[6]](#latinscript).
Using the `code` property of `keydown` event [[5]](#keycode), should be possible to check for numeric keys without ambiguity,
as the `code` property returns the keycode before keymapping is applied.

    let shortcutHandler = (event) => {
        if (event.code === 'Digit2' && event.metaKey === true && event.shiftKey) {
            // This also catches "Meta+Shift+2" on Latin Script based layouts
            console.log('"Meta+Shift+2" pressed')
        }
    }

### Further readings

- Internationalize your keyboard controls by Julien Wajsberg, Mozilla Hacks, <a href="https://hacks.mozilla.org/2017/03/internationalize-your-keyboard-controls/" target="_blank">https://hacks.mozilla.org/2017/03/internationalize-your-keyboard-controls/</a>
- Can I Use KeyboardEvent.key, Can I Use, <a target="_blank" href="https://caniuse.com/#feat=keyboardevent-key">https://caniuse.com/#feat=keyboardevent-key</a>
- Can I Use KeyboardEvent.code, Can I Use, <a target="_blank" href="https://caniuse.com/#feat=keyboardevent-code">https://caniuse.com/#feat=keyboardevent-code</a>

### References

1. Keypress Event Types - DOM 3 Level Specifications, W3C, <a href="https://www.w3.org/TR/DOM-Level-3-Events/#events-keyboard-types" target="_blank" id="keypress">https://www.w3.org/TR/DOM-Level-3-Events/#events-keyboardevents</a>
2. Key Mapping, W3C, <a href="https://www.w3.org/TR/DOM-Level-3-Events/#key-mapping" target="_blank" id="keymapping">https://www.w3.org/TR/DOM-Level-3-Events/#key-mapping</a>
3. `key` Property of KeyboardEvent, W3C, <a href="https://www.w3.org/TR/DOM-Level-3-Events/#key-algorithm" target="_blank" id="keyproperty">https://www.w3.org/TR/DOM-Level-3-Events/#key-algorithm</a>
4. Modifier Key, Wikipedia, <a href="https://en.wikipedia.org/wiki/Modifier_key" target="_blank" id="modifier">https://en.wikipedia.org/wiki/Modifier_key</a>
5. Key Codes, W3C, <a href="https://www.w3.org/TR/DOM-Level-3-Events/#keys-codevalues" target="_blank" id="keycode">https://www.w3.org/TR/DOM-Level-3-Events/#keys-codevalues</a>
6. QWERTY-based layouts for Latin script, Keyboard Layout, Wikipedia, <a href="https://en.wikipedia.org/wiki/Keyboard_layout#QWERTY-based_layouts_for_Latin_script" target="_blank" id="latinscript">https://en.wikipedia.org/wiki/Keyboard_layout#QWERTY-based_layouts_for_Latin_script</a>

_-- 22/05/2017_


Keyboard Shortcuts and Layouts in the Browser

Defining layout independent keyboard shortcuts in the browser


**July 2018 UPDATE:** I've released the source code of this project on github.</br>
Find out more here: [https://github.com/cybercase/up2_hacking](https://github.com/cybercase/up2_hacking)

### Having fun with Jawbone UP2

A few months after releasing [UpNotifications for UP24](../up24_notifications)
I received a lot of emails asking to add support for the new **Jawbone UP2**.

As soon as Jawbone made the UP2 available outside the US I placed my order,
and after receiving the new band, without thinking too much I started tuning the UpNotifications
source code to include the UP2 among supported devices just to see if the same hack used for UP24 was working also on this band...

> Unfortunately, it was not.

I didn't give up, and following the same steps of my own [UP24 Hacking](../up24_reverse_engineering) blogpost,
I opened Android Studio, turned on the debugger, started intercepting calls to the android BLE API and see what has changed with respect to UP24...

The bluetooth packets I was reading were completely different from the UP24 packets,
so I thought that maybe it was just a matter of replacing the old UP24's pairing command with the new UP2's one. And so I did.

I soon found out that the same trick of _sending a pairing command to make the band vibrate_ was not working because
the new UP2 knows if it has been already paired with a phone, and in that case it does not vibrate on pairing.

While the UP24 **allowed anyone** to make vibrate your band without your permission just by sending a pairing command,
with the UP2 **Jawbone has fixed this issue**. Though this is a good news for all UP2 owners, this meant that I had to
find another way to trigger the vibration.

> I needed to go deeper.

I struggled to understand how the communication protocol has changed, and see if I could find another command to exploit.
But just looking at the stream of bluetooth packets wasn't enough...

so I though of disassembling the app and inspecting its `.smali` source code using [apktool](http://ibotpeaches.github.io/Apktool/)
to search for anything that could be useful.

After going through the sources for a while I noticed a `log` method used all over the app, probably for debugging purposes,
that was disabled just by a simple flag check.

In a file called `JBLog.smali`, I changed the following lines

```
-    if-nez v0, :cond_0
+    if-eqz v0, :cond_0
```

then reassembled the app and installed into my phone.

> I started getting a lot of debug information placed there right from UP developers :)

I immediately found out that the communication protocol was much more sophisticated than the one used for UP24.

Log messages like this

```
8257-8288/com.jawbone.upopen I/UPOPEN﹕ StreamService >>> writeOutputStream > KeyExchangeRequest >
    f >> (0, 63, 0) > 0x03
    g >> (1, 63, 0) > 0x00
    h >> (2, 63, 0) > 0xd3
    i >> (3, 63, 0) > 0x10
    d >> (4, 63, 0) > 7FA19B1353FC584CAEF3D4214C74A365
```

and

```
8257-7505/com.jawbone.upopen D/SecuredStream﹕ generateSeed > 271372323671BDEE846276EF48B53F75
8257-7505/com.jawbone.upopen D/SecuredStream﹕ 8200CD05803A090000 xor D4CB772B8B9D389527 = 56CBBA2E0BA7319527
```

and

```
8257-7505/com.jawbone.upopen I/UPOPEN﹕ StreamService >>> writeOutputStream > SecureChannelRequest >
    f >> (0, 63, 0) > 0x06
    g >> (1, 63, 0) > 0x00
    h >> (2, 63, 0) > 0xd0
    i >> (3, 63, 0) > 0x10
    c >> (4, 63, 0) > F9FC5162DC8B609B6F891BC88648A49A
    d >> (4, 63, 0) > null
```

were suggesting that the protocol was relying on some kind of encryption to communicate over a secure channel, using a shared encryption key exchanged at the time of pairing.

> I needed more, so I thought of using a decompiler.

I tried some like [Procyon](https://bitbucket.org/mstrobel/procyon/), [CFR](http://www.benf.org/other/cfr/) to get as much information as possible. With the help of a great tool called [BytecodeViewer](https://github.com/Konloch/bytecode-viewer), I stared to follow the code paths, drawing diagrams, understand the app flow and structures...

Eventually I reproduced all the steps needed to pair and setup an encrypted communication channel with the UP2 and send the vibration command I needed :)

<iframe class="line-11-m line-17-d" src="//www.youtube.com/embed/uwsyjyM5GJU" frameborder="0" allowfullscreen></iframe>

> Victory! ... almost.

As I came back on my initial goal of integrating UP2 support into UpNotifications, I realized that it would be very hard to achieve any kind of _user friendly_ experience.

The first problem comes from the fact that the encryption key is kept secret into the original UP application, and the only way to retrieve such key is to have a _rooted_ phone.

The second crucial problem is that, even if it was possible to get the encryption key easily, UP2 supports only one bluetooth connection at time.
This means that an _UpNotifications for UP2_ would not work while the band is connected to the original UP application.

And since there's no way (without root permission) to control when the UP app runs or communicates with the band, **UpNotifications for UP2 would be incompatible with the official UP app**.

> I still haven't decided whether write an _UpNotifications for UP2_ or not...

~~So, for the time being, I'm not releasing the source code of the "test" app I wrote~~ (moreover, currently the code is quite a mess).

Also, I want to be sure of the legal consequences of releasing any protocol specs...

Unlike the old UP24, Jawbone is using this protocol on devices like UP4 for [contactless payments](https://jawbone.com/blog/introducing-up4/), so this time they could be much more interested in keeping the protocol as much secret as possible to avoid security issues.

_-- 19/09/2015_


UP2 Reverse Engineering


# UpNotifications for Jawbone UP24

**UPDATE**: Google has changed a how the app should ask for the `READ_SMS, RECEIVE_SMS` permissions. Unfortunately I've not been able to update UpNotifications and this resulted in the app being removed from the Play Store.
I'm leaving here a link to the APK for anyone who's interested in trying out the app. Just keep in mind that I won't be able to provide any support.

[UpNotifications APK Download](https://www.dropbox.com/s/9jkqaxjod6ilmkn/upnotifications.apk?dl=0)

### Intro

After my last blog post on [UP24 Reverse engineering](../up24_reverse_engineering) I received a lot emails about the Android application I wanted to write for myself to receive notifications on the jawbone up24 band.

During the last month I found the time to write such app and release a [demostration video](https://www.youtube.com/watch?v=JFcVZpmnbII) of how it works.

### First release

Time has come to make this application publicly available, ~~and here you can have it for just a small fee that will allow me to keep the app up-to-date:
<a href="https://play.google.com/store/apps/details?id=me.brilli.stefano.upnotifications" target="_blank">Download UpNotifications for UP24</a>.~~

### Requirements

- Official UP Application
- An UP24 band paired with your device
- Firmware version 3.0.21 running on your band

### Disclaimer

This application has been widely tested and it is proven to work correctly; actually the author itself use this app on a daily basis to get calls and sms notifications on its wrist.

However it is important to state that this application is the result of a reverse engineering process, hence:

- It may interfere with normal functioning of the band
- It may drain your band battery
- It may stop working anytime (especially after band's software update)
- It may not work with all band versions

### Privacy Policy

Read here the [UpNotifications privacy policy](/upnotifications_privacy)

### Legal Notice

This product is not affiliated with, nor endorsed or licensed in any way by Jawbone.
Jawbone, UP, and UP24 are trademarks or registered trademarks of Jawbone corporation. All rights reserved.

_-- 21/03/2015_


UpNotifications for Jawbone UP24


# UP24 Hacking

### Intro

Last month I received a [Jawbone UP24](http://jawbone.com/store/buy/up24) as birthday gift, and after a couple of weeks of _standard use_ I couldn't resist digging into its technical side to discover how this device actually works.

As far as I discovered, UP24 features a 3 axis accelerometer, 2 notification leds, a vibrating motor and a Bluetooth LE interface to communicate with the companion smartphone app "UP" (available for Android and iOS). Technical readers can find further info and a complete teardown of the _low-end_ version of UP24 (the older UP) [here](http://www.eevblog.com/forum/blog/eevblog-412-jawbone-up-pedometer-teardown/).

The strength of UP24 comes also from the great companion app that let users configure alarms and notifications in response of activities or events. Great features are the _smart alarm_ that chooses the best time to wake you up in the morning, and _idle notifications_ that reminds you to stretch your legs after being too much time idle on the chair.

The UP24 is definitely meant to be an activity band, and I think this is the sole reason why the guys ad Jawbone decided (at the time of writing) to not provide some extra useful features (IMO) like notifications on email/sms/calls/etc...

<iframe class="line-17-d line-11-m" src="//www.youtube.com/embed/fVznagkOwo0" frameborder="0" allowfullscreen></iframe>

### Beginning

I wanted to use my UP24 as a notification device for messages coming from some of my android phone's contacts... something simple, like a _vibrate on sms_.

So, as usual, the first question is

> " has someone already solved my problem? "

Googling around I found [something here](http://www.plutinosoft.com/hacking-bluetooth-le/) and [here](https://forums.adafruit.com/viewtopic.php?f=8&t=51450).
... Perfect! Just no code available, and wrong OS :)

However, thanks to these blogposts I knew it was possible to make vibrate my UP on command, and it had to be done through some custom Bluetooth LE command.

### Learning

After learning the basics of Bluetooth LE ([here's](https://www.usenix.org/conference/woot13/workshop-program/presentation/ryan) one of the most interesting article I found) I needed to find out how to use it on my Android.

Found a great example and all the necessary documentation [here](http://developer.android.com/samples/BluetoothLeGatt/index.html), and after installing Android Studio I was ready to start!

### Doing

Using the example from Android SDK I was able to list all the services of my UP24 in matter of minutes... However I still hadn't a clue of what services, attributes, and values I had to exploit to make the UP24 vibrate.

> Then I thought of debugging the process on my phone

to see what was happening behind the scene while issuing a vibrate command. Note, there isn't any _vibrate command_ in UP application, but I noticed that after a successful bluetooth pairing the band vibrates; and that was exactly the reaction I wanted to use for my custom-notifications app.

After connecting my phone to the Android Studio debugger I did set a breakpoint for UP's process to break at `BluetoothGatt.writeCharacteristic` method... This made everything _a lot_ slower both on my old phone and laptop but in the end, after a successful pairing, I got what I wanted :)

> -20 32 8 16 4 53 1 0 16 0 1 125.

And by the end of the day I was able to record the video at the top of this page.

<div class="mtop-1-m mtop-1-d line-16-d line-13-m" style="text-align: center;">
    <img src="/images/up24_pairing.jpg" alt="Successful UP24 Pairing" style="width: 100%;"/>
</div>

### Epilogue

I'm still writing my custom-notifications app, nevertheless I'm not releasing any of the source code of this project due to possible legal issues. However, for any _mid-level_ programmer should be easy to achieve the same results just by following the steps of this blogpost.

### Assignment

I also managed to make some experiments in order to reverse engineer a couple of the _sniffed_ values... what if you change the previous value to "-20 32 8 16 4 53 1 0 **3** 0 1 125" ? :)

_-- 10/11/2014_


UP24 Hacking


# Pre-commit Hook

## PEP8 Version

A couple of days ago I've refactored and enhanced my pre-commit hook to check also for PEP8 compliancy of Python source files. To achieve this I used the pep8 tool that you can easily install with:

`pip install pep8`

And here's the new pre-commit hook:

    #!/bin/bash
    #
    # TAB CHECK:
    #
    # Searches tab characters in staged changes.
    # To specify file extensions to check use "hooks.notabs" variable.
    # Extensions are separated by "|".
    # Eg:
    #   git config hooks.notabs html|js
    #
    # PEP8 CHECK:
    #
    # run pep8 on all python staged files.
    # To specify pep8 command options use "hook.pep8options" variable
    #
    # Eg:
    #   git config hook.pep8 "--ignore=E226,E302"

    exec 1>&2

    notabs=$(git config hooks.notabs)
    notabs_error=0
    for f in `git diff --cached --name-only | egrep "\.("$notabs")$"`
    do
        lines=`git show :$f | fgrep -n $'\t'`
        if [ -n "$lines" ]; then
            echo "TAB(s) found in:" $f "at line(s)"
            echo $lines
            notabs_error=1
        fi
    done

    if [ $notabs_error -eq 1 ]; then
        echo
        echo "Remove all TAB(s) characters and stage again your changes."
        echo
        exit 1
    fi

    pep8_options=$(git config hooks.pep8options)
    pep8_error=0
    for f in `git diff --cached --name-only | egrep ".py$"`
    do
        git show :$f | pep8 --format=$f":%(row)d:%(col)d: %(code)s %(text)s" $pep8_options -
        if [ $? -eq 1 ]; then
            pep8_error=1
        fi
    done

    if [ $pep8_error -eq 1 ]; then
        echo
        echo "Your commit is cause of one or more PEP8 error(s)"
        echo
        echo "Please fix these errors and stage again your changes"
        echo
        exit 1
    fi

This new version is quite straightforward so I'm not digging too much into it.
The two main changes are:

- Discover of command `git show` :)
- Add pep8 style test

About the latter point, it's important to say that the pep8 has becomes one of the requirements to use this hook. Also, you can configure your pep8 options by typing:

`git config --add hooks.pep8options "--ignore=E121,E122" # this ignores Error 121, 122`

A complete list of errors and warnings of pep8 tool is available here: http://pep8.readthedocs.org/en/latest/intro.html#error-codes

PS.

I'm using this hook just from a couple of days, so it may (probably) have some bugs... feel free to contribute at <https://github.com/cybercase/funproject/blob/master/experiments/pre-commit> ;)

_-- 15/09/2013_


Pre-commit Hook - PEP8 Version


# Pre-commit Hook

The project on which I'm working has acquired some young people recently.

For a couple of them it's even their first working experience so I'm really
trying to transmit them the importance of conventions and an uniform coding style.

It's usual (and perfectly normal) to find some coding style mistakes in their commits.
So, to help us happily code all together, I created a small pre-commit hook
to put in our repositories.

Right now it's just a simple no-tabs check, but with some small changes it could
check for use of deprecated functions or some forgotten `import pdb; pdb.set_trace()` :)

    # Files extensions in hooks.notabs are separated by "|"
    # Eg:
    #   git config hooks.notabs py|js

    exec 1>&2
    notabs=$(git config hooks.notabs)
    toplevel=$(echo "`git rev-parse --show-toplevel`/" | sed -e 's/[\/&]/\\&/g')
    if [ -n "$notabs" ] &&
        git diff --cached -- not_a_file `git diff --cached --name-only |
          egrep '\.('$notabs')$' |
          sed 's/^/'$toplevel'/g' | xargs` |
          egrep -qn $'^\+\.*\t'
    then
        echo "Error: Attempt to add TABS"
        echo
        echo "Do you really want to break our beautiful coding conventions? :("
        echo
        echo "Remove all tabs characters and stage again your changes."
        echo
        echo "To override this hook use:"
        echo
        echo "  git commit --no-verify"
        echo
        exit 1
    fi

To have it working:

copy this script into `repository_dir/.git/hooks/pre-commit`.
Add some file extensions to hooks.notabs variable (these must be separated by |).
Done!

Let's look at each parts in rigorous order of execution

- `notabs=$(git config hooks.notabs)`: retrieves from local config the files extensions to check

- `git diff --cached --name-only`: lists names of files that have staged changes

- `egrep '\.('$notabs')$'`: removes files having different extensions from the ones in notabs

- `sed 's/^/'$toplevel'/g'`: prepend the absoulute path to each filename

- `xargs`: creates a list of arguments using previous file names list

- `git diff --cached -- not_a_file`: returns staged changes for files coming from "xargs". Note that "not_a_file" is an unexistant file, specified in case that the output of xargs is empty. In fact if no files are specified the "git diff --cached" command would return staged changes for every file.

- `egrep -qn '^\+\.*\t'`: searches for all the lines starting with "+" and containing a tab

Note that this pre-commit hook can be easily bypassed using.

`git commit --no-verify`

This reflects exactly the same thought I want communicate to my collegues. Everyone should
struggle to pass the pre-commit hook checks, but no one should be forced to.

References:

1. [Customizing-Git-Git-Hooks](http://git-scm.com/book/en/Customizing-Git-Git-Hooks)

_-- 13/08/2013_


Pre-commit Hook


# Python 3 Metaprogramming

How can you import XML files into Python 3?
And why you would?
... This blogpost doesn't answer this last question, but it's definetly going to answer the first one :)

Everything I'm writing is taken from this talk from David Beazley: [youtube video](https://www.youtube.com/watch?v=sPiWg5jSoZI).
Consider this post as a very little summary of its contents.

Let's start with the requirements:
Python 3.3
... that's all!

And let's see what you're getting:

If you define a file structures.xml like this

    <structures>
        <structure name="Stock">
            <field type="SizedString" maxlen="4">name</field>
            <field type="PosInteger">shares</field>
            <field type="PosFloat">price</field>
        </structure>
    </structures>

At the end of this blogpost you will get this

    >>> from structures import *
    >>> s = Stock("GOOG", 100, 99.0)
    >>> # DEFAULT INITIALIZER
    >>> s.name, s.shares, s.price
    ('GOOG', 1, 1.0)

    >>> # TYPE CHECKING
    >>> s.name = 100
    TypeError: Expected <class 'str'>

    >>> # CONSTRAINT CHECKING
    >>> s.name = "GOOOOOOG"
    ValueError: Too big

So, if this just aroused your curiosity, go on reading ;)

The first step is to have a look at descriptors.
Descriptors is just how properties are implemented in python [see this link]. In this example, we use them as classes to perform checks on values assignment.
So, let's take as example a descriptor that performs a check such that only values of type str within a certain length are allowed.

    class StringDescriptor:
        def __init__(self, name, maxlen):
            self.name = name
            self.maxlen = maxlen

        def __set__(self, instance, value):
            if type(value) != str:
                raise TypeError("Wrong type, expected: %s" % str(str))
            elif len(value) > self.maxlen:
                raise ValueError("String too long")
            instance.__dict__[self.name] = value

        def __get__(self, instance, cls):
            # Actually performs the default action. Just don't define this
            # method to get the default behavior.
            return instance.__dict__[self.name]

    class Stock:
        name = StringDescriptor("name", 4)
        def __init__(self, name):
            self.name = name

    >>> st = Stock("GOOG")
    >>> st.name = "GOOOOOG"
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
      File "post.py", line 10, in __set__
        raise ValueError("String too long")
    ValueError: String too long

    >>> st.name = 1

    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
      File "post.py", line 8, in __set__
        raise TypeError("Wrong type, expected: %s" % str(str))
    TypeError: Wrong type, expected: <class 'str'>

    To handle different descriptors, David uses a descriptors hierarchy like the following:
    class Descriptor:
        def __init__(self, name=None):
            self.name = name
        def __set__(self, instance, value):
            instance.__dict__[self.name] = value
        def __delete__(self, instance):
            raise AttributeError("Can't delete")

    class Typed(Descriptor):
        ty = object
        def __set__(self, instance, value):
            if not isinstance(value, self.ty):
                raise TypeError('Expected %s' % self.ty)
            super().__set__(instance, value)

    class Sized(Descriptor):
        def __init__(self, *args, maxlen, **kwargs):
            self.maxlen = maxlen
            super().__init__(*args, **kwargs)
        def __set__(self, instance, value):
            if len(value) > self.maxlen:
                raise ValueError('Too big')
            super().__set__(instance, value)

    class String(Typed):
        ty = str

    class Integer(Typed):
        ty = int

    class Float(Typed):
        ty = float

Then merges the descriptors using multiple inheritance... But pay attention at MRO! (method resolution order)

    class Positive(Descriptor):
        def __set__(self, instance, value):
            if value < 0:
                raise ValueError('Expected >= 0')
            super().__set__(instance, value)

    class PosInteger(Integer, Positive):
        pass

    class PosFloat(Float, Positive):
        pass

Finally to get rid of the repeated variable's name in the descriptor constructor, David use a metaclass to inject the name into the descriptor:

    class StructMeta(type):
        def __new__(cls, name, bases, clsdict):
            fields = [ key for key, val in clsdict.items()
                    if isinstance(val, Descriptor) ]
            for name in fields:
                clsdict[name].name = name
            clsobj = super().__new__(cls, name, bases, clsdict)
            return clsobj

The Stock class definition now becomes

    class Stock(metaclass=StructMeta):
        name = SizedString(maxlen=4)
        shares = PosInteger()
        price = PosFloat()

        def __init__(self, name, shares, price):
            self.name = name
            self.shares = shares
            self.price = price

There is still another "problem" that David try to solve: the code repetition inside the **init** method.
To address this problem, he changes the previous metaclass as follows.
from collections import OrderedDict

    class StructMeta(type):
        @staticmethod
        def __prepare__(cls, name, bases=None):
            # this method returns the dictionary used by the class instance.
            # To generate a signature the parameters order is crucial, so an
            # OrderedDict is used
            return OrderedDict()

        def __new__(cls, name, bases, clsdict):
            fields = [ key for key, val in clsdict.items()
                    if isinstance(val, Descriptor) ]
            for name in fields:
                clsdict[name].name = name

            # the following block generates the code for __init__ method
            if len(fields):
                init_code = 'def __init__(self, %s):\n' % \
                            ', '.join(fields)
                for name in fields:
                    init_code += '    self.%s = %s\n' % (name, name)
                exec(init_code, globals(), clsdict)

            clsobj = super().__new__(cls, name, bases, dict(clsdict))
            return clsobj

And the Stock class becomes

    class Stock(metaclass=StructMeta):
        name = SizedString(maxlen=4)
        shares = PosInteger()
        price = PosFloat()

At this point it's convenient introduce a Structure base class:

    class Structure(metaclass=StructMeta):
        pass

    class Stock(Structure):
        name = SizedString(maxlen=4)
        shares = PosInteger()
        price = PosFloat()

And finally we get to the XML part :)
The first goal is to generate the python code from the XML file. To achieve this the David use these functions:

    from xml.etree.ElementTree import parse
    def _xml_to_code(filename):
        doc = parse(filename)
        code = ''
        for st in doc.findall('structure'):
            code += _xml_struct_code(st)
        return code

    def _xml_struct_code(st):
        stname = st.get('name')
        code = 'class %s(Structure):\n' % stname
        for field in st.findall('field'):
            name = field.text.strip()
            dtype = field.get('type')
            kwargs = ', '.join('%s=%s' % (key, val)
                                for key, val in field.items()
                                if key != 'type')
            code += '    %s = %s(%s)\n' % (name, dtype, kwargs)
        return code

And the result of parsing the structure.xml file (defined at the beginning of the blogpost) is:

    >>> print(_xml_to_code("structures.xml"))
    class Stock(Structure):
        name = SizedString(maxlen=4)
        shares = PosInteger()
        price = PosFloat()

The final step consists in hooking to the python import system. Full details about the new Import Hooks feature of Python3.3 are found at [PEP-302].
We begin defining a new importer class to append at sys.meta_path

    import os
    class StructImporter:
        def __init__(self, path):
            self._path = path
        def find_module(self, fullname, path=None):
            name = fullname.rpartition('.')[-1]
            if path is None:
                path = self._path
            for dn in path:
                filename = os.path.join(dn, name+'.xml')
                if os.path.exists(filename):
                    return StructXMLLoader(filename)
            return None

And an XML module loader

    import imp
    class StructXMLLoader:
        def __init__(self, filename):
            self._filename = filename
        def load_module(self, fullname):
            mod = sys.modules.setdefault(fullname,
                                        imp.new_module(fullname))
            mod.__file__ = self._filename
            mod.__loader__ = self
            code = _xml_to_code(self._filename)
            # actually this is bad. I should use mod.__dict__
            # instead of globals(), and add an import statement into
            # "code" to load Structure and the other classes.
            exec(code, globals(), mod.__dict__)
            return mod

    import sys
    def install_importer(path=sys.path):
        sys.meta_path.append(StructImporter(path))

    install_importer()

    And finally here we are:
    Python3.3 -i xmlimport.py
    >>> from structures import *
    >>> s = Stock("GOOG", 1, 1.0)

You can find the final version of the xmlimporter.py and structures.xml under the folder

`python_metaprogramming` in my git repository at:

`git://github.com/cybercase/funproject.git`

If you got 3 hours to spend, and a lot of love for this metaprogramming stuff, I really suggest to watch the entire video from David Beazley. Also, I apologize in advance for any error in this blogpost.

_-- 22/05/2013_


Experimenting with Python 3 Metaprogramming

Python 3 Metaprogramming


# Holidays and GPU

Next week I am visiting London.

In the meanwhile enjoy a code preview of A GPU Exercise part 1 and part 2.
To get, compile, and test the code, clone my funproject repository on github.

    git clone git://github.com/cybercase/funproject.git

To compile the code is required the _NVIDIA CUDA Toolkit_. Then run:

    cd funproject
    cmake .
    make

If CUDA Toolkit was found by CMake, then the lev_distance target should be built into the experiments directory. To quickly test the performances run:

    cd experiments
    ./lev_distance lev_distance.cu thread.h

The following result is achieved on my late 2010 MBA

    lev_distance.cu size is 8716 bytes
    thread.h size is 17818 bytes
    LevDistance...
    elapsed time: 9.240 (s)
    CudaLevDistance...
    elapsed time: 0.872 (s)
    Results matches!
    Distance: 14332

Please note that this is an educational implementation, and several improvements can be done to exploit all the features of the underlying architecture...

But before talking about this... holidays! :)

_-- 25/09/2012_


Post about my GPU project before vacation

Holidays and GPU


This is the sequel of previous post: [A GPU Exercise - part 1](./gpu_exercise)

Let's resume from the algorithm for computing the Levenshtein distance among two strings. To fill every cell of the subrpoblems matrix, we can allocate a 2 dimensional array and then proceed like this:

    // C-Like syntax: don't expect this compiles :)
    int lev_distance(char* string_one, char* string_two) {
      int m = strlen(string_one)+1;
      int n = strlen(string_two)+1;
      int matrix[m][n];

      for (int j=0; j < n; ++j) { // Step1: Init first row
        matrix[0][j] = j;
      }

      for (int i=0; i < m; ++i) { // Step2: Init first column
        matrix[i][0] = i;
      }

      for (int i=1; i < m; ++i) { // Step3: Fill every cell
        for (int j=1; j < n; ++j) {
          if (string_one[i-1] == string_two[j-1]) {
            matrix[i][j] = matrix[i-1][j-1];
          } else {
            matrix[i][j] = min(matrix[i][j-1],
              matrix[i-1][j],
              matrix[i-1][j-1]) + 1;
          }
        }
      }
      return matrix[m-1][n-1]; // cell containing cost of the real problem
    }

But, if we look carefully at Step3 inner loop, it's easy to see that there is not need to store the entire matrix since, for each cell, we need just the immediately preceding ones. Hence, to reduce allocated memory, it's possible to change the algorithm like this:

    int lev_distance(char* string_one, char* string_two) {
      int m = strlen(string_one); // Note: removed +1
      int n = strlen(string_two)+1;

        int current[n];
        int previous[n];
        for (int j=0; j < n; ++j) {
            previous[j] = j;
        }

        for (int i=0; i < m; ++i) {
            current[0] = i+1;
            for (int j=1; j < n; ++j) {
            // Note: the if is replaced by the conditional assignment
                current[j] = (previous[j]+1, current[j-1]+1,
                  previous[j-1] + (string_one[i] != string_two[j-1] ? 1 : 0) );
            }
            swap(current, previous);
        }
        return previous[n-1];
    }

Now, only 2 array of size `strlen(string_two)+1` are stored.

This algorithm is quite good for a singlecore cpu implementation, since it has good data locality... Small strings can be stored entirely inside the cache memory to achive the best performances. However, think about optimising this algorithm for a multicore CPU... It's easy to notice the strong data dependancy: we can't compute the value of a cell if we didn't already computed the previous ones.

To overcome this problem and take the full advantage of using multiple cores we need to change the algorithm. And these are the changes (can you find another way?).

Instead of walking over the matrix by rows and then by columns, we can walk by diagonals to avoid some data dependancies. Look at the followings steps:

Compute the value of cell $$c_{1,1}$$ (previous needed values $$c_{1,0}$$ $$c_{0,1}$$ and $$c_{0,0}$$ comes from initialisation)

<div class="line-5-m line-5-d text-center">

$$\begin{array}{|c|c|c|c|c|c|} \hline _{X}\backslash^{Y} & \# & y_1 & y_2 & y_3 & \cdots \\ \hline \# & 0 & 1 & 2 & 3 \\ \hline x_1 & 1 & \mathbf{c_{1,1}} \\ \hline x_2 & 2\\ \hline x_3 & 3 \\ \hline \vdots\\ \hline \end{array}$$

</div>

Compute cells $$c_{2,1}$$ and $$c_{1,2}$$: cell $$c_{2,1}$$ requires cells $$c_{1,1}$$ (computed in the previous step), cell $$c_{2,0}$$ and $$c_{1,0}$$ (both comes from initialisation). Same for cell $$c_{1,2}$$.

<div class="line-5-m line-5-d text-center">

$$\begin{array}{|c|c|c|c|c|c|} \hline _{X}\backslash^{Y} & \# & y_1 & y_2 & y_3 & \cdots \\ \hline \# & 0 & 1 & 2 & 3 \\ \hline x_1 & 1 & c_{1,1} & \mathbf{c*{1,2}} \\ \hline x_2 & 2 & \mathbf{c*{2,1}} \\ \hline x_3 & 3 \\ \hline \vdots \\ \hline \end{array}$$

</div>

Compute cell $$c_{3,1}$$ $$c_{2,2}$$ and $$c_{1,3}$$: cell $$c_{2,2}$$ requires cells $$c_{1,1}$$ (computed in step 1) $$c_{2,1}$$ and $$c_{1,2}$$ (from step 2)

<div class="line-5-m line-5-d text-center">

$$\begin{array}{|c|c|c|c|c|c|} \hline _{X}\backslash^{Y} & \# & y_1 & y_2 & y_3 & \cdots \\ \hline \# & 0 & 1 & 2 & 3 \\ \hline x_1 & 1 & c_{1,1} & c*{1,2} & \mathbf{c*{1,3}} \\ \hline x*2 & 2 & c*{2,1} & \mathbf{c*{2,2}} \\ \hline x_3 & 3 & \mathbf{c*{3,1}} \\ \hline \vdots \\ \hline \end{array}$$

</div>

And so on...
At a given step, each cell refers to the cells computed in the previous steps, and never to the ones of the same. Precisely, filling the cells in step $$i$$ requires filling cells at step $$i-1$$ and $$i-2$$.

This allow us to rewrite the algorithm in a way such that all of the cells in a certain diagonal can be filled concurrently since the data dependancy has been moved among diagonals.

Unfortunately I don't have enough time to show the pseudo code of this algorithm in this post because, even if this new algorithm can be conceptually simple to understand, a good implementation requires the handling of a some special cases that will make the code snippet definitely too long to explain in this blogpost...

Instead, I'm going to push (and talk about) the code on my github account during the next blogpost.

... suspense is raising, isn't it? :)

_--16/09/2012_


A GPU Exercise - part 2


# A GPU Exercise

## Part 1

It's been several months since the last time I put my hands on something related to GPUs. Sadly, I get very rarely the chance to get this kind of jobs.
So, to keep myself trained (just in case I will get one), during the last two weeks I worked on an "exercise project".

For this exercise project I choosed to port to GPU an algorithm that I studied during my University years. [Here you can find some informations](http://en.wikipedia.org/wiki/Levenshtein_distance):

I'll try to explain in few words and with a little example what is the Levenshtein distance.
Given two strings, the Levenstein distance is the minimum number of character insertion, deletion or substitution, to change a string into the other, ie:

The Levenshtein distance between RISOTTO and PRESTO is 4:

1. Insert P
2. Substitute I with E
3. Delete O
4. Delete T

Finding the shortest list of operations to change a string into another is a problem that can be solved by using the Dynamic Programming technique. The main trouble is that, in many cases, this technique requires an huge amount of memory to store intermediate results and avoid recomputing.

In fact, this algorithm requires a amount of memory proportional to the product of the lengths of the 2 strings: if len(string1) is m, and len(string2) is n, then the memory and operations requirement is O(m\*n).

The required memory amount can be reduced in several ways... expecially exploiting some of the upper bounds of the optimal solution (see the wikipedia link at the top of this article).

However, if we compute just the number of operations (without actually knowing which operations are performed), the memory requirement can be reduced up to O(max(m, n)), even though the number of operations remains unchanged at O(m\*n).

Let's try to understand how the algorithm works, and hence, why computing the optimal cost, in terms of number of changes, is cheaper (in terms of memory) than computing the entire operations list.

Given two string $$X$$ and $$Y$$ such that $$X=x_1,x_2,...,x_m$$ and $$Y=y_1,y_2,...,y_n$$ , we can use a matrix to represent the solutions of each subproblem.

<div class="line-5-m line-5-d text-center">

$$\begin{array}{|c|c|c|c|c|c|} \hline _{X}\backslash^{Y} & \# & y_1 & y_2 & \cdots & y_n \\ \hline \#\\ \hline x_1\\ \hline x_2\\ \hline \vdots\\ \hline x_m\\ \hline \end{array}$$

</div>

Where cell $$i,j$$ will contain the cost of the optimal solution for the subproblem of changing string $$X_i=\#,x_1,x_2,...,x_i$$ into $$Y_i=\#,y_1,y_2,...,y_j$$ with $$i \leq m$$ and $$j \leq n$$. The $$ \# $$ character represents the empty string.
Note that the first row and column of this matrix, are quite easy to fill:

The first column contains the costs of changing any of the $$X$$ substrings into the empty $$\#$$ string. So, substring $$X_1$$ (formed by the empty string plus the $$x_1$$ character) will require 1 deletion to change into substring $$Y_0$$ (the empty string)... $$X_2$$ will require 2 deletion, $$X_3$$ is 3, and so on...
The first row contains the cost of changing the empty string into the substring $$Y_j$$. So, the cost of changing the empty string into $$Y_1$$, will be 1 insertion, $$Y_2$$ is 2, and so on...
Obviusly, the cell $$0,0$$ containing the cost of changing $$\#$$ in $$\#$$, that is 0.

<div class="line-5-m line-5-d text-center">

$$\begin{array}{|c|c|c|c|c|c|} \hline _{X}\backslash^{Y} & \# & y_1 & y_2 & \cdots & y_n \\ \hline \# & 0 & 1 & 2 & \cdots & n\\ \hline x_1 & 1\\ \hline x_2 & 2\\ \hline \vdots\\ \hline x_m & m\\ \hline \end{array}$$

</div>

Now that we have defined the base cases, we can look at how it's possible to fill the remaining cells, and thus finding the costs of the optimal solutions. Let's take as example the cell $$1,1$$ corresponding to subproblem of changing $$X_1=\#,x_1$$ into $$Y1=\#,y_1$$.

The easiest case is when $$x_1=y_1$$. In this case we don't need to perform any operation over the previous subproblem of changing $$X_0$$ into $$Y_0$$, hence the costs are the same.

If $$x_1$$ differs from $$y_1$$, then we can choose the cheapest among the three following options:

- Substitute $$x_1$$ with $$y_1$$. The cost will be 1 plus the cost of changing $$X_0$$ into $$Y_0$$.

- Insert the character $$y_1$$ to $$Y_0$$. The cost will be 1 plus the cost of changing $$X_1$$ into $$Y_0$$

- Delete the character $$x_1$$ from the string $$X_1$$. the cost will be 1 plus the cost of changing $$X_0$$ into $$Y_1$$
  In the same way it's possible to compute the values for all the other cells, by looking at the cells associated to the immediately preceding subproblems. In the end we will get the value of subproblem $$(X_m, Y_n)$$, that is the problem from which we started from.

Let's make some observations:

- The value of cell $$(j,i)$$ depends only from the comparison between $$x_i$$ and $$y_j$$ and value in cells $$(j-1,i-1)$$, $$(j-1,i)$$, $$(j,i-1)$$.

- The operation that was performed to produce the value in cell $$(i,j)$$ can be deduced only by looking at $$x_i$$ and $$y_j$$ and value inside cells $$(j-1,i-1)$$, $$(j-1,i)$$, $$(j,i-1)$$.

This makes easy computing the value of a cell $$i,j$$ since we have to remember just the values of the immediatly preceeding subproblems.
On the other hand, to retrive all the operations associated to the optimal solution, it's necessary to store (or recompute) the values of all the preceeding cells, since it's not possible to know which cells you will need, until you know the "subproblems path" to the optimal solution.

I hope you enjoied this simple introduction to the algorithm. In the next post I'm going straight into the implementation and the problems (and the solutions) of make run this algorithm on a GPU... attaching a lot of code of course :)

And naturally, if you spot errors, I would be really happy to receive reports ;)

_--13/09/2012_


A GPU Exercise - part 1


# Debug Pointer: a quick overview
Let's focus on some keypoints of my debug_ptr:

- What a debug_ptr is used for?
  A debug_ptr can be used like a standard pointer type to hold the address of a dynamically allocated object:
  `typedef_pointer(int*, int_p); int_p p = new int(0);`

- How could it be useful?
  If you forget to delete a dynamically allocated object before loosing its last reference, you are probably creating a memory leak. A debug_ptr warns you about this fact using a warning policy.


    struct ThrowPolicy {
        ThrowPolicy() {
            throw std::runtime_error("lost reference to undeleted object");
        }
    };
    struct PrintPolicy {
        PrintPolicy() {
            std::cerr << "WARNING: lost reference "
                            "to undeleted object" << std::endl;
        }
    };

- How much does it cost? (in performance terms)
  The features of debug_ptr are mostly useful in "debug mode". In a production release, you may not want use the features of a debug_ptr class (although you can), because of the performance losses due to the reference counting.

- How did I address this issue?
  You can compile your software by defining ENABLE_DEBUG_TYPES to get the debug_ptr feature turned on. Otherwise all the debug_ptr features are turned off by a macro that will substitute any occurrence of debug_ptr<T> with a T*. This will avoid any overhead at compile and run time.


    #ifndef ENABLE_DEBUG_TYPES
    #define typedef_pointer(Type, Alias, ...) typedef Type Alias
    #define typedef_array(Type, Alias, ...) typedef Type Alias
    #else // ENABLE_DEBUG_TYPES
    ...
    #endif

- How debug_ptr syntax differs by the one of a standard pointer type?
  debug_ptr it's intended to be used just like any other smart_ptr, and in most of the cases you should not notice any difference in creating, copying, dereferencing, assigning, and deleting...


    typedef_pointer(int*, int_p);
    int_p p = new int(0);
    int_p p_other = new int(0);
    *p = 63;
    int_p p_other = p;
    delete p_other;

- How did you get the same delete syntax of a standard pointer type?
  By defining a default cast operator to a pointer-to-deleter-class. The cast operator will be implicitly called and a new deleter object returns to operator delete. So, delete operator, deletes the deleter-class.


    operator deleter*() const {
        return deleter::new_deleter(pd_);
    }


And that's all folks!

If you have any question, just leave a comment.
If you like this project, or have any other ideas about what could be the next step of the debug_ptr, fork the project on github and have fun :)


    git clone git://github.com/cybercase/debug_ptr.git # clone the repo
    cd debug_ptr
    g++ -Wall -o test debug_ptr_test.cc -DENABLE_DEBUG_TYPES
    ./test

_--01/09/2012_


C++ Smart Pointer for Debugging - Design Decisions

Debug Pointer: a quick overview


# Debug Pointer

As I mentioned in the last post, lately I'm working on a C++/Boost software (aka speeding up and refactoring an unmaintainable software). This software is just a kind of parser. It parses several binary files and, for each one, produces a xml file. Also it needs to merge and summarise some of the fields contained in each one of these files to produce a _Final Report_ xml file.

There may be several way to write a software for a task like this, and the customer choosed to use threads. A big mistake, because (IMHO) Who wrote the software did not have any idea of how use threads efficently, and he ended up using a lot of locks and semaphores everywhere... but this is another story.

The most impressive thing that I saw in this software was the inconsiderate abuse of Boost shared pointers. These were used almost everywhere in the software in every nonsense way they could be used... passing them around by copy or just like the following:

    for (int i=0; i<SOMEINT; ++i) {
        // Why not: SOMECLASS sp; ???
        boost::shared_ptr<SOMECLASS> sp(new SOMECLASS);
        sp->SomeMethod();
    }

Just by fixing these kind of misuses, I've got a speedup of over 2x.

Shared pointers can be really useful but they:

- should be used with care because they can become really expensive
- should not be used just to avoid thinking about memory management in your software

And the last point is the one that I felt was the case of this software. For this reason, and for helping myself to refactor and remove shared pointers from this software, I wrote my own smart pointer: **debug_ptr**.

**debug_ptr** is a smart pointer that should help the developer to manage the memory correctly (a delete for every new). A debug_ptr just warn the developer when he forgets to delete an dynamically allocated object, so that he can insert the correct delete (or `delete[]`) statement.
Also, debug_ptr is designed in a way such that, once you have tested your software and no memory leaks warning are raised anymore, it can be automatically substituted with a native pointer type, so that no overhead is added both at run and compile time.

For now you can check the debug_ptr source code and have a look at the few test cases that show how it can
be used. It's located in my debug_ptr repository on github:

    git clone git://github.com/cybercase/debug_ptr.git # clone the repo
    cd debug_ptr
    g++ -Wall -o test debug_ptr_test.cc -DENABLE_DEBUG_TYPES
    ./test

In the next post, I'll try to focus on some interesting parts of this very simple smart pointer.

_--22/08/2012_


Debug Pointer


# The concept of minimum

It's been a while from my last post on this blog... Too much work and too few spare time :-/

However lately, I'm reading a lot! It's much easier for me to find out the time to read an article, or source code from some project, than writing my own code... Writing good code takes actually not little time, so I thought that I can share some of my readings with the few readers of this blog. Better than nothing, isn't it?

So, let's start with this old article from Dr.Doobs <http://drdobbs.com/cpp/184403774> I just finished to read.
I would never thought that a so simple question about implementing the min and max C macros using C++ templates would require such a long answer (and code).

Even though lately I'm starting to think not-so-good about C++ (but this is not the post to talk about this), I find this kind of problems so mind teasing.

And also... look at the author of the article! Yes, it's him :)

_--10/03/2012_


The concept of minimum


# Sorting Priorities

Let's say you have your 3d colored point type:

    struct MyPoint
    {
        // A 3d colored point
        MyPoint(int c, int x, int y, int d) :
                 color(c), x(x), y(y), d(d) {}
        int color;
        int x;
        int y;
        int d;
    };

You define a vector of `MyPoint` objects carefully ordered by color, depth, height and width.

    int width = 100;
    int height = 100;
    int depth = 5;
    int colors = 2;

    int len = width * height * colors * depth;
    std::vector<MyPoint> pts;
    pts.reserve(len);

    for (int c=0; c<colors; ++c)
        for (int d=0; d<depth; ++d)
            for (int y=0; y<height; ++y)
                for (int x=0; x<width; ++x)
                    pts.push_back(MyPoint(c, x, y, d));

Then one of your funny colleagues put a

    std::random_shuffle(pts.begin(), pts.end());

just the line before you are scanning the ordered array of `MyPoint`... If it's not a colleague, could be that you need to apply a transformation matrix to all of your points, or whatever else that will break the color, depth, height and width ordering of your set.

To order back your vector by the same priorities, you can use the STL sort algorithm with some custom comparison function.
The the first function I wrote was this:

    bool mypoint_all_sort_fn(const MyPoint& p0, const MyPoint& p1)
    {
        if (p0.color < p1.color)
            return true;
        else if (p0.color == p1.color)
            if (p0.d < p1.d)
                return true;
            else if (p0.d == p1.d)
                if (p0.y < p1.y)
                    return true;
                else if (p0.y == p1.y)
                    if (p0.x < p1.x)
                        return true;
        return false;
    }

and then `std::sort(pts.begin(), pts.end(), mypoint_all_sort_fn);`

I found this solution the ugliest among the others. It's not scalable, has too many indentations and strong code dependancy... And also if `mypoint_all_sort_fn` was defined as operator inside `MyStruct` declaration I wouldn't like to have such a function inside my software.

The second solution I came to was using several `stable_sort`

    bool mypoint_x_sort_fn(const MyPoint& p0, const MyPoint& p1)
    {
        return p0.x < p1.x;
    }
    bool mypoint_y_sort_fn(const MyPoint& p0, const MyPoint& p1)
    {
        return p0.y < p1.y;
    }
    bool mypoint_d_sort_fn(const MyPoint& p0, const MyPoint& p1)
    {
        return p0.d < p1.d;
    }
    bool mypoint_c_sort_fn(const MyPoint& p0, const MyPoint& p1)
    {
        return p0.color < p1.color;
    }

and then

    std::stable_sort(pts.begin(), pts.end(), mypoint_x_sort_fn);
    std::stable_sort(pts.begin(), pts.end(), mypoint_y_sort_fn);
    std::stable_sort(pts.begin(), pts.end(), mypoint_d_sort_fn);
    std::stable_sort(pts.begin(), pts.end(), mypoint_c_sort_fn);

I found this solution not too bad by the code style point of view, but it's not the same about performances. More are the values you want to sort by, more are the stable_sort steps you have to do.

The last solution, which I found the most fascinating one, was suggested to me by two of my collegues, and it took me a just a small bunch of time to write the code down.

    template <typename T> int element(const T&, int i);

    template <typename T, int I> struct Orderer
    {
        static bool compare(const T& t0, const T& t1)
        {
            if (element(t0, I) == element(t1, I))
                return Orderer<T, I-1>::compare(t0, t1);
            else
                return element(t0, I) < element(t1, I);
        }
    };
    template <typename T> struct Orderer<T, -1>
    {
        static bool compare(const T& t0, const T& t1)
        {
            return false;
        }
    };

Using templates it's possible to make the compiler generate the ugly if-else code. Then the task of providing the right element for the sorting is demanded to an element(int) function. Also, it's possible substitute the element(int) function with an element(int) member function (or maybe an operator) in `MyPoint` definition. This is how it work:

    template <> int element<MyPoint>(const MyPoint& p, int i)
    {
        // Watch out!
        // The higher is the i-value, the most significant is the member
        switch(i)
        {
            case 3:
                return p.color;
            case 2:
                return p.d;
            case 1:
                return p.y;
            case 0:
                return p.x;
            default:
                throw std::invalid_argument("Undefined element");
        }
    }
    bool mypoint_sort(const MyPoint& t0, const MyPoint& t1)
    {
        return Orderer<MyPoint, 3>::compare(t0, t1);
    }

and then `std::sort(pts.begin(), pts.end(), mypoint_sort);`

That's it! A more readable switch-case statement provides the priority of sorting.... and the `mypoint_sort` function call the template right specialization of Orderer Struct static compare function.

Here how you can find, compile and run the code for this example:

    git clone git://github.com/cybercase/funproject.git
    cd funproject/other
    g++ order.cpp -o order -Wall

One interesting thing I discovered while writing the code of this example, is that you can't use template function specialization. I found a discussion about this topic at <http://www.gotw.ca/publications/mill17.htm>. The Peter Dimov and Dave Abrahams example shows why template specialization can't be done with functions.

_-- 15/01/2012_


Sorting Priorities


# Inspiration Code

## Part 3

The last of these three parts summary is about `_thread` and `Result` structures.

`_thread` is a just a container for `pthread_t` and `pthread_attr_t` thread variables. It provides a wrapper for pthread_create and pthread_detach functions, and a member variable for storing the called function return value... However the most important task accomplished by this structure is reference counting.

    template <typename T> struct _thread
    {
        // This struct will hold the return value of the thread called func.

        _thread() : counter(0)
        {
            pthread_attr_init(&attr);
            pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
        }

        ~_thread() { pthread_detach(thd); }

        T result;
        pthread_t thd;
        pthread_attr_t attr;
        volatile int counter;

        int join() { return pthread_join(thd, NULL); }
        int start(void*(f)(void*), void* v)
        {
            return pthread_create(&thd, &attr, f, v);
        }

        // Atomic function for add and sub
        int inc() { return __sync_fetch_and_add(&counter, 1); }
        int dec()
        {
            if (__sync_fetch_and_sub(&counter, 1) == 0)
                delete this;
            return counter;
        }

        private:
        _thread(const _thread&);
        _thread& operator=(const _thread&);
    };

`_thread` has both inc/dec member functions that are called everytime the structure instance is referenced/dereferenced by some other object. When the dec member function is called and the counter becomes zero, then the destructor is invoked and `_thread` is deleted. Also, the destructor calls `pthread_detach`, so that thread's resources can be freed.

This reference counting mechanism is very important since we want that `_help_fn` and `_help_st` saves the computation results in a place from which we can fetch the result...

To clarify: we can't just launch the thread (that executes `_help_fn`), save the results and delete everything. We need to be sure that we are deleting the result at the right time.

This is why, when a new thread is created, the corresponding `_thread` object is referenced both by a `_help_st` and a `Result` object. In this way, at the end of `_help_fn`, when `_help_st` is deleted, the dec function of `_thread` object is called by `_help_st` destructor...
But `_thread` object is deleted only if also the corresponding `Result` object is already deleted.

    template <typename T> struct Result
    {

        Result(_thread<T>* thd) : thd(thd)
        {
            thd->inc();
        }

        Result(const Result<T>& o)
        {
            thd->inc();
            thd = o.thd;
        }

        Result<T>& operator=(const Result& o)
        {
            o.thd->inc();
            thd->dec();
            thd = o.thd;
            return *this;
        }

        T value()
        {
            switch (thd->join())
            {
                case 0:
                  break;
                case EINVAL:
                  throw std::runtime_error("EINVAL on pthread_join");
                  break;
                case EDEADLK:
                  throw std::runtime_error("EDEADLK on pthread_join");
                  break;
                case ESRCH:
                  // Thread already exited
                  break;
            }
            return thd->result;
        }

        ~Result()
        {
            thd->dec();
        }

        _thread<T>* thd;
    }

The `Result` object is the one that is returned to the user who started a new thread. So, if the user keep it, he can fetch the return value through the `Result` object.
Otherwise the `Result` object is automatically destroyed and corresponding `_thread` object is deleted when dec is called by `_help_st` destructor.

To close this last part, here are the static methods of `Thread` class for creating a new thread that runs a function, a functor or an instance method having one argument. The signature is similar for functions, functors, and instance methods having more than one arument.
As you see the return value of these function is a `Result` object.

    template <typename T, typename O, typename I0> static Result<T>
    run(O obj, I0 a0)
    {
        _functor1<T, O, I0> o(obj, a0);
        return Result<T>(_start<T>(o));
    }

    template <typename T, typename I0> static Result<T>
    run(T(*fun)(I0), I0 a0)
    {
        _functor1<T, T(*)(I0), I0> f(fun, a0);
        return Result<T>(_start<T>(f));
    }

    template <typename T, typename C, typename I0> static Result<T>
    run(C* c, T(C::*fun)(I0), I0 a0)
    {
        _class_functor1<T, C, I0> f(c, fun, a0);
        return Result<T>(_start<T>(f));
    }

Returning `Result` object is assigned a `_thread` object, created by `_start` helper function in `Thread` class.

    template <typename T, typename F> static _thread<T>*
    _start(const F& functor)
    {
        _thread<T>* mythread = new _thread<T>();
        _help_st<T, F >* h2 = new _help_st<T, F>(mythread, functor);
        mythread->start(_help_fn<_help_st<T, F> >, h2);
        return mythread;
    }

I hope you enjoyed this post serie... If you have question or you need some clarification, just leave a comment. I will be happy to answer or rewrite the unclear part

_-- 29/12/2011_


Code I wrote after reading a book - third part

Inspiration Code - part 3


# Inspiration Code

## Part 2

Since the `pthread_create` function signature allows running of `void*(*)(void*)` function type only, I was quite sure on packaging into a struct both the callable object and its args, and pass them to some function matching that signature. Here is the "some function" I named `_help_fn`:

    template <S> void* _help_fn(void* v)
    {
        // This function signature match the one needed by
        // pthread_create func.
        S* st = (S*)v;
        st->exec();
        delete st;
        return NULL;
    };

The `S` template parameter is meant to be the type of a package struct. The exec() method from this struct should call any callable type, together with its arguments and, obviously, write somewhere the return value of the call.
This is how I wrote the package struct, named `_help_st`.

    template <typename T, typename I> struct _help_st
    {
        _help_st(_thread<T>* t, I f) : functor(f)
        {
            thd = t;
            thd->inc();
        }

        ~_help_st()
        {
            thd->dec();
        }

        I functor;
        _thread<T>* thd;

        void exec()
        {
            thd->result = functor();
        }
    };

For now, don't pay too much attention to the `_thread` member variable... You just need to know that this member variable holds the result of thread's computations.
I assigned `exec()` member function just the task of storing the returned value by a some callable object. The return value type is told by template parameter `T`. Then, the dirty job of calling the function with all of its args is left to a functor object of type `I`.

I didn't find any other way than writing as many functors as needed to match all of the previously told callable types.
This is the functor for instance method pointers receiving one arg:

    template <typename T, typename C, typename I0> struct _class_functor1
    {
        _class_functor1(C* c, T(C::*m)(I0), I0 a0) : m(m), c(c), a0(a0) {}
        T operator()() { return (c->*m)(a0); }
        T(C::*m)(I0);
        C* c;
        I0 a0;
    }

And this is the functor for all the other kinds of callable objects receiving one arg:

    template <typename T, typename O, typename I0> struct _functor1
    {
        _functor1(O obj, I0 a0) : o(obj), a0(a0) {}
        T operator()() { return o(a0); }
        O o;
        I0 a0;
    }

I needed a special functor object like `_class_functor1` for handling instance methods. This is because C++ don't provide a way to store the callable result of `(c->*m)`.

_-- 20/12/2011_


Code I wrote after reading a book - second part

Inspiration Code - part 2


# Inspiration Code

A couple of week ago I run into Modern C++ Design, a book from Andrei Alexandrescu.
I read it all the way in just a few days. That was so fascinating! This book shows
you the unknown and magic power of template metaprogramming... a kind of _avada kedavra_ of C++.

I've got uncertain reviews from my colleagues about this book... But my opinion is definitely a ten out of ten.

But now, let's get to the topic! Just a few day ago, I started writing some code for one of my so-called "funprojects". A snippet of code contained in thread.h file to wraps pthreads functions with a Thread class. After few attempts I decided that my Thread class should be able to execute everything that is a callable in C++.

From Modern C++ Design, here is the list of entities that support operator `()`.

- C-like functions
- C-like pointers to functions
- References to functions
- Functors (object that defines operator() )

The result of applying operator `.*` or operator `->*` having a pointer to a member function in the right-hand side of the expression.
The behavior that I was trying to achieve for any of them was

`RETURN_TYPE result = Thread::run(some_callable, arg1, arg2, ...);`

And this is what I've got in the end

    // main.cpp
    #include <iostream>
    #include "thread.h"
    int myfun(int i)
    {
        std::cout << "myfun received: " << i << std::endl;
        return i*2;
    }

    class myclass
    {
    public:

        myclass(int i) : i(i) {}

        int mymember(int k)
        {
            std::cout << "mymember received: " << k << std::endl;
            return i*2;
        }
        int i;

        int operator()(int j)
        {
            std::cerr << "operator received: " << j << std::endl;
            return i*2;
        }

    };

    int main(int argc, char** argv)
    {

        int (*mypt)(int) = &myfun;
        int (&myref)(int) = myfun;
        myclass mc(5);

        // Call to function
        Result<int> r0 = Thread::run(myfun, 0);
        std::cout << "retval:" << r0.value() << std::endl;

        // Call to function pointer
        Result<int> r1 = Thread::run(mypt, 1);
        std::cout << "retval:" << r1.value() << std::endl;

        // Call to function reference
        Result<int> r2 = Thread::run(myref, 2);
        std::cout << "retval:" << r2.value() << std::endl;

        // Call to functor
        Result<int> r3 = Thread::run<int>(mc, 3);
        std::cout << "retval:" << r3.value() << std::endl;

        // Call to member function pointer
        Result<int> r4 = Thread::run(&mc, &myclass::mymember, 4);
        std::cout << "retval:" << r4.value() << std::endl;

        return 0;
    }

In the next post I'm going to show some details of the code in `thread.h`.

Want to compile and run this code?!

    git clone git://github.com/cybercase/funproject.git
    cd funproject/other
    g++ concurrent.cpp -o concurrent -Wall # add -lpthread if you are on a linux system

_-- 19/12/2011_
