The deflate algorithm

The deflate algorithm, the compression approach used in the original Pkzip 2.0 version, is a fascinating read defined in the RFC1951 standard.  In order to understand the spec, it's helpful to work through the "hello" examples discussed in this article.

Section 3.2.2. in the RFC defines the basic approach to creating Huffman trees, but this article provides a solid explanation about how it works and shows how it's implemented.   The key insight is that Huffman codes are generated by counting the lengths of the variable-length codes (For more background/context, see Stanford lectures on algebraic error control codes and/or the textbook used in the class).

Gzip is essentially using the deflate algorithm but adds a header/trailer to the end.  RFC1952 provides a breakdown of how the header is generated, but you can also test for yourself:

$echo "hello" > hello

$gzip hello

$python

>>> data = open("hello.gz", "r").read()

>>> data[0:2]

'\x1f\x8b'

>>> data[3:4]

'\x08'

>>> [hex(ord(a)) for a in data[4:8]]

['0x9e', '0x2e', '0xfa', '0x50']

>>> 0x50fa2e9e
1358573214
>>> datetime.datetime.fromtimestamp(1358573214)
datetime.datetime(2013, 1, 18, 21, 26, 54)

>>> data[10:16]
'hello\x00'

More related articles too:

http://www.zlib.net/manual.html
http://www.adayinthelifeof.nl/2010/06/02/deflating-the-universe/
http://www.w3.org/Graphics/PNG/RFC-1951#codes
http://www.commandlinefanatic.com/cgi-bin/showarticle.cgi?article=art007

RSA block type is not 02 error

Ever seen the error message "block type is not 02" when performing RSA decryption via M2Crypto?  It's a direct result of an RSA decryption not succeding.  Before data is encrypted, it's padded with a header and a block type of 01 or 02, depending on whether the public or private key was used.  If the private key was used, the RFC spec (http://www.ietf.org/rfc/rfc2313.txt) says that the padded header should be 01 (though it also says 00 can be used).  If the public key was used to encrypt the data, the RFC header will be set the BT block to 02:

A block type BT, a padding string PS, and the data D shall be
   formatted into an octet string EB, the encryption block.

              EB = 00 || BT || PS || 00 || D .           (1)

   The block type BT shall be a single octet indicating the structure of
   the encryption block. For this version of the document it shall have
   value 00, 01, or 02. For a private- key operation, the block type
   shall be 00 or 01. For a public-key operation, it shall be 02.

During the decryption phase, the RSA encryption algorithm first converts things back to a block of data (ultimately each block is converted from an integer) and then does one additional verification process against this block type.   If the block type doesn't match 01 or 02, it's likely the wrong key was used to decrypt.   You have the wrong decryption key, may be not using the private key if the public key was used to encrypt, or the public key if the private key was used.  (In the latter two cases, just the other pair has to be used to reverse the original operation.)

Negative modulo's

This function from http://qugstart.com/blog/ruby-and-rails/facebook-base64-url-decode-for-signed_request/ basically tries to add extra padding characters before attempting to base64-decode a string:

  # Pad the encoded string with "+".
  data += "=" * (4 - (len(data) % 4) % 4)
  return base64.urlsafe_b64decode(data)

Django has the equivalent function in its django.core.signing library:

def b64_decode(s):
    pad = '=' * (-len(s) % 4)
    return base64.urlsafe_b64decode(s + pad)

The code from Django's function uses negative modulo to compute the vaule. How do negative modulos work?    See this excerpt from http://mathforum.org/library/drmath/view/52343.html:

The mod function is defined as the amount by which a number exceeds the 
largest integer multiple of the divisor that is not greater than that 
number. In this case, -340 lies between -360 and -300, so -360 is the 
greatest multiple LESS than -340; we subtract 60 * -6 = -360 from -340 
and get 20:

-420 -360 -300 -240 -180 -120  -60   0   60   120  180  240  300  360
--+----+----+----+----+----+----+----+----+----+----+----+----+----+--
       | |                                                    |  |
   -360| |-340                                             300|  |340
       |=|                                                    |==|
        20                                                     40

Working with a positive number like 340, the multiple we subtract is 
smaller in absolute value, giving us 40; but with negative numbers, we 
subtract a number with a LARGER absolute value, so that the mod 
function returns a positive value. This is not always what people 
expect, but it is consistent.

If you want the remainder, ignoring the sign, you have to take the 
absolute value before using the mod function.

How LinkedIn's JS API implements JavaScript parameters

If you've looked at LinkedIn's API, you may have noticed that they follow a curious approach to providing script parameters to an external JavaScript file:

https://developer.linkedin.com/documents/configuration-and-compatibility

<script type="text/javascript" src="http://platform.linkedin.com/in.js">
  api_key:    [API_KEY]
  onLoad:     [ONLOAD]
  authorize:  [AUTHORIZE]
</script>

Initial inspection seems to suggest that you are declaring three separate JavaScript variables: api_key, onLoad, and authorize. In actuality, you are just defining text inside the script tag that gets parsed with a bunch of regexeps and removing of whitespaces.

Basically the code below appears to extract out the innerHTML and then set the variables r and K to be the key/value pairs. White spaces are removed with the replace() function.

http://platform.linkedin.com/in.js

        try {
            m = f.innerHTML.replace(A, n)
        } catch (z) {
            try {
                m = f.text.replace(A, n)
            } catch (y) {
            }
        }
    }
    m = m.replace(J, "$1").replace(A, n).replace(F, n);
    aa = C.test(m.replace(j, n));
    for (var T = 0, S = m.split(k), q = S.length; 
    T < q; 
    T++) {
        var s = S[T];
        if (!s || s.replace(j, n).length <= 0) {
            continue
        }
        try {
            V = s.match(g);
            r = V[1].replace(A, n);
            K = V[2].replace(A, n)
        } catch (X) {
            if (!aa) {
                console.warn("script tag contents must be key/value pairs separated by a colon. Source: " + X)
            }
            continue
        }
        N(r, K)
    }

Some of the regexpes are defined at the top of in.js:

var R = {
        "bootstrapInit": +new Date()
    }, p = document,
        l = (/^https?:\/\/.*?linkedin.*?\/in\.js.*?$/),
        b = (/async=true/),
        D = (/^https:\/\//),
        J = (/\/\*((?:.|[\s])*?)\*\//m),
        F = (/\r/g),
        j = (/[\s]/g),
        g = (/^[\s]*(.*?)[\s]*:[\s]*(.*)[\s]*$/),
        x = (/_([a-z])/gi),
        A = (/^[\s]+|[\s]+$/g),
        u = (/^[a-z]{2}(_)[A-Z]{2}$/),
        C = (/suppress(Warnings|_warnings):true/gi),
        d = (/^api(Key|_key)$/gi),

OAuth2: The Road to Hell

http://hueniverse.com/2012/07/oauth-2-0-and-the-road-to-hell/

http://hueniverse.com/2010/09/oauth-2-0-without-signatures-is-bad-for-the-web/


RealtimeConf - "OAuth 2.0 - Looking Back and Moving On" by Eran Hammer from &yet on Vimeo.

Upgrading NetworkManager and ModemManager with Ubuntu 12.04

Ever since I've upgraded to Ubuntu 12.04, I've noticed that Franklin U600 USB modem disconnects are frequent (especially when moving in a train ride) and prevent you from reconnecting to the USB device unless you reboot. Upgrading to the latest Ubuntu packages doesn't seem to resolve the issue. One of the main issues appears to be that the ModemManager that comes with Ubuntu 12.04 runs on version 0.5, which appears to have some stability issues with random disconnects (possibly because of this issue with modem disconnects, callbacks, and weak references).

To try to understand better, I started to dig into Modem Manager. Modem Manager has a Wiki article about troubleshooting. To prevent modem-manager from being restarted each time it was killed, I simply renamed the /usr/bin program and then started the program manually by using the –debug flag. After numerous tries of watching the modem get disconnected, I noticed that this state change seemed to occur quite a bit. During the disconnection process, the modem would suddenly jump back to the connected state:

Nov 12 08:49:37 my-laptop modem-manager[8862]:   Modem /org/freedesktop/ModemManager/Modems/0: state changed (connected -> disconnecting)
Nov 12 08:49:37 my-laptop NetworkManager[8912]:    SCPlugin-Ifupdown: devices removed (path: /sys/devices/virtual/net/ppp0, iface: ppp0)
Nov 12 08:49:37 my-laptop modem-manager[8862]:   Modem /org/freedesktop/ModemManager/Modems/0: state changed (disconnecting -> connected)

ModemManager 0.6.0 appears to fix these issues, as well as introduce a new approach for writing plugins for the package.

Currently Ubuntu 12.04 don't have the latest packages for ModemManager, and the issue was severe enough to compel me to try to compile the latest version myself (http://ftp.gnome.org/pub/gnome/sources/ModemManager/):

sudo apt-get install libdbus-glib-1-dev
sudo apt-get install libgudev-1.0-dev
wget 
./configure
make
sudo apt-get uninstall modem-manager
make install

I've been running with the latest 0.6.4 version and the problem doesn't happen anymore. If the connection drops, the modem will eventually be made available again in the Network Manager applet.

Another problem I've noticed is that the Network Manager applet often has blank entries for VPN connections, which appears to be a reported bug. I've also encountered issues with the Gigabit Ethernet port not reliably connecting with a longer cable, so finally decided to take the hit to try to install the latest versions of Network Manager and the Network Manager applet. There is also the issue that the Network Manager applet fails to respond to any mouse clicks, though typing "nmcli nm wwan on" enables the Mobile Broadband option.

These issues all seemed to necessitate upgrading Network Manager from the standard Ubuntu 12.04 packages. Be forewarned: if you attempt this process, you could easily disable your ability to access the Internet. Without the magic that NetworkManager does to handle all your wired and wireless connections, you will then have to resort to using ifconfig to setup a static IP address (i.e. ifconfig eth0 192.168.1.xxx), setting up a static default gateway (route add default gw 192.168.1.1), and adding a nameserver entry in /etc/resolv.conf (nameserver x.x.x.x). So I'd strongly suggest you try this process out on a local network unless you're adept at also connecting to wireless LAN's via the command line.

Download the latest version of Network Manager from this address:
http://ftp.gnome.org/pub/GNOME/sources/NetworkManager/0.9/

Unpack the files and make sure you have these dev libraries installed:

sudo apt-get install intltool
sudo apt-get install libnl-dev 
sudo apt-get install uuid-dev
sudo apt-get install libnss3-dev
sudo apt-get install ppp-dev
./configure --sysconfdir=/etc --libexecdir=/usr/lib/NetworkManager --localstatedir=/var
make

At this point, you should avoid doing any make installs. You want to make sure both Network Manager and the Network Manager applet compiles without any issues before removing them. See http://projects.gnome.org/NetworkManager/developers/ since there are also different compile options in the instructions.

Note: The -sysconfdir is set to /etc, which will allow the compiled version of NetworkManager to find your current configuration (in /etc/NetworkManager). This way, you can re-use all your wired, wireless, and mobile broadband connections. The -libexecdir is needed since default Ubuntu installs dump the DHCP/PPTP scripts inside this directory, which are whitelisted by AppArmor. If you start seeing Permission Denied errors, chances are your paths are being blocked by AppArmor. You also need the -localstatedir option for this same reason, since this directory speicifies where the DHCP client will try to write the PID data.

The Network Manager can be downloaded from this location:

http://ftp.gnome.org/pub/GNOME/sources/network-manager-applet/0.9/network-manager-applet-0.9.6.4.tar.xz

tar xvfp network-manager-applet-0.9.6.4.tar.xz
sudo apt-get install libgconf2-dev
sudo apt-get install libgnome-keyring-dev 
sudo apt-get install libnotify-dev 
sudo apt-get install libgtk-3-dev 
./configure --sysconfdir=/etc --libexecdir=/usr/lib/NetworkManager
make

Note: if you try to compile with libgtk2.0-dev, chances are that the compile will fail. Network Manager needs GTK 2.0+ to compile, but on Ubuntu 12.04 it seems that the libgtk-3-dev library is really what is needed.

If the compiles were successful, now is the time to remove Network Manager. Be forewarned that at this point you could easily block your ability to access the Internet. So only proceed to this point if you're confident enough to recover.

sudo apt-get remove network-manager
sudo apt-get purge network-manager-gnome && sudo apt-get install network-manager-gnome

The --libexecdir for the Network Manager is needed for invoking other plugins, such as VPN. Also, if you intend to use VPN, you'll also need to git clone the repo you need to use (in this case, we're cloning the PPTP module).

git clone git://git.gnome.org/network-manager-pptp
cd network-manager-pptp/
./autogen.sh --sysconfdir=/etc --libexecdir=/usr/lib/NetworkManager --localstatedir=/var
make
sudo make install

You can then do make installs in both project directories and attempt to start Network Manager (or logging out and logging back in)

Note: if you don't see the nm-applet at the top, here are a few places to check. The first requires using the dconf-editor, which needs to be apt-get installed:

apt-get install dconf-tools
dconf-editor

The instructions to use dconf-editor are listed here, which is basically to make sure that notifications are not disabled in the nm-applet namespace: http://askubuntu.com/questions/150406/how-do-i-re-enable-disabled-network-notifications-in-gnome-shell

You also want to make sure using dconf-editor that the com.canonical.Unity.Panel systray-whitelist is set toto "['all'] (or at least to include nm-applet). I found that my system tray was not set to this value and therefore prevented nm-applet from being rendered:

http://askubuntu.com/questions/136733/some-system-tray-icons-invisible-in-gnome-classic-12-04

Normally I wouldn't recommend trying to compile and install Modem Manager and Network Manager, but the current packaged versions supplied in Ubuntu 12.04 appear to be so buggy and unstable that this approach appears to help deal with many of the issues that have been reported.

Uploading videos to SmugMug

If a video upload fails, SmugMug allows you to view your Upload Log in your Settings page to see the error. However, the wrong video resolution causes it to return an "invalid video codec." After trying all different types of formats (WebM, H.264, FLV), I finally succeeded by converting the video from its original format of 400x224 to 320x240, which seemed to resolve the problem.

avconv -i <MP4 input file> -s 320x240 <output file>

There isn't much documentation on SmugMug's site to give you any indication that it's the resolution size that has to be adjusted:

http://help.smugmug.com/customer/portal/articles/84569-how-to-convert-and-format-a-video-for-upload-to-smugmug

Side note: if you want to flip the audo/video streams, here's how you do it.   The first "0:1:0" map parameter means to take file input 0 (since you can have multiple input files) and take stream 1 and map it to stream 0.   You do the same for stream 1 of input file 0 and map to stream 0.

avconv -i <input file 0> -vcodec copy -acodec copy -map 0:1:0 -map 0:0:1 <output file>