How to get started chatting on freenode with XChat on Ubuntu

What’s needed ahead of time

  • A computer with Ubuntu installed
  • The ability to use sudo on Ubuntu
  • An e-mail address to use for freenode account registration and for password recovery
  • About half an hour (more in the unlikely event a freenode administrator is not available for a while)

Anonymity

Skip this section if you’re not trying to maintain anonymity

I can’t help you to perfectly protect your anonymity, since there are thousands of little unnoticeable ways that your identity can be uncovered. I can give you some optional tips to reduce the risk a bit, though.

  1. Use the following alternative procedure:
    1. Go to a place where you usually use the Internet
    2. Set up MAC address randomization on your WiFi card
    3. Turn off your DHCP hostname
    4. Install Tor; press Ctrl-Alt-T to open a terminal and type:
      sudo apt-key adv --recv-keys --keyserver keyserver.ubuntu.com 886DDD89
      sudo add-apt-repository "deb http://deb.torproject.org/torproject.org $(lsb_release -s -c) main"
      sudo apt-get install -y deb.torproject.org-keyring
      sudo apt-get install -y tor
      exit
      
    5. Install whichever of Firefox or Chrome that you don’t use
    6. Install the Tor Browser Bundle
    7. Follow only the Install XChat section below
    8. Use a firewall to block all Internet activity for all applications on the computer except DHCP, Tor, the newly-installed browser, the Tor Browser, and XChat
    9. Ensure that XChat is not connected to any servers and will not connect when it’s started up
    10. Completely quit the newly-installed browser (you shouldn’t have started it yet) and the Tor Browser
    11. Take the batteries out of your mobile devices
    12. Travel to an open WiFi hotspot that:
      • …you haven’t used before
      • …isn’t in your neighborhood
      • …isn’t in your friends’ neighborhoods
      • …isn’t in a small town or small city that you spend much time in
      • …is somewhere you can blend in with all the other people using that hotspot
      • …is somewhere you don’t have to do anything nearby that’s recorded (sign-in sheets, credit card use, library card use, enter a username or password that’s unique to you, etc.)
      • …is somewhere that cameras aren’t recording you
    13. With the newly-installed browser:
      1. Start the browser
      2. Go to Google
      3. Handle any WiFi sign-in screens
      4. Quit the browser
    14. With the Tor Browser:
      1. Quit the browser completely if it’s running
      2. Start the browser
      3. Sign up for a webmail account (perhaps at bitmessage.ch), using the following rules:
        • Don’t enter any real information about yourself
        • Don’t enter any pseudonymous information you use anywhere else
        • Don’t enter any of your other e-mail addresses or account names
        • The webmail provider can break into your freenode account if they’re untrustworthy, so choose providers wisely
        • Use only a recently-updated Tor Browser with this webmail account
        • If the Tor Browser is already running, completely quit it and restart it right before accessing webmail
        • When you’ve started the Tor Browser for webmail, do nothing else in the Tor Browser (including using another webmail account for another freenode account) until you’re done with webmail and you’ve completely quit the Tor Browser and restarted it
        • When you’re done with webmail, sign out and then completely quit the Tor Browser; do both
        • Never send any messages from this webmail account, ever
        • When you receive a message, quickly deal with it so that you don’t need it anymore, then delete it, then empty the trash
        • Never give out this e-mail address to anyone (including friends) or to any Internet sites, except to NickServ when registering for this one freenode account; if you want an e-mail address for another freenode account or for any other purpose, use a completely separate e-mail account
      4. Leave the browser running for the freenode registration confirmation message
    15. Successfully complete this guide, starting with Set up an SSL connection to freenode; do not skip the Tor section
    16. With the Tor Browser:
      1. Delete the registration e-mail and empty the trash
      2. Completely quit the Tor Browser
    17. Quit XChat completely
    18. Disconnect from WiFi
    19. Leave back to a place you’re more familiar with
    20. Put the batteries back in your mobile devices
    21. Uninstall the newly-installed non-Tor-Browser browser, making sure to delete all of its files
    22. Reconfigure or disable the firewall so that it doesn’t block normal applications anymore
    23. You’re done; XChat is now ready for use anywhere

Install XChat

  1. Press Ctrl-Alt-T to open a terminal window, and type the following:
    sudo apt-get install -y xchat xchat-otr
    mkdir ~/.xchat2
    cd ~/.xchat2
    wget http://lwsitu.com/xchat/cap_sasl_xchat.pl
    exit
    

Set up an SSL connection to freenode

  1. Start XChat by going to the Ubuntu application menu, Internet submenu, XChat IRC
  2. In the XChat: Network List window that comes up, do the following:
    1. Fill out the form:
      • Nick name: what you will normally be called (up to 16 characters, no spaces, made of alphanumeric, _, -, \, [, ], {, }, ^, `, or |)
      • Second choice: your backup nickname if your normal nickname is temporarily unavailable
      • Third choice: your backup nickname if both your normal nickname and the earlier backup nickname are both temporarily unavailable
      • User name: a name for you that shows up next to your Internet address whenever you do anything on IRC; usually your normal nickname, but it can be whatever you’d like (up to 9 characters, no spaces, made of alphanumeric, ., _, or -)
      • Real name: a short message for people who ask the server who you are; can be your real name, a pseudonym, a short quote, the URL for your website, or whatever you’d like
    2. Check next to Skip network list on startup
    3. Choose FreeNode from the Networks list
    4. Click the Edit... button, and do the following in the new window:
      1. Click on irc.freenode.net/8001
      2. Change it to irc.freenode.net/7000
      3. Check next to Connect to selected server only
      4. Check next to Auto connect to this network at startup
      5. Check next to Use SSL for all the servers on this network
      6. Click Close
    5. In the original window, click Connect
  3. If it asks What would you like to do next?, click OK to close the window
  4. In the new main window, check that it shows the MOTD (message of the ‘day’) and that you’ve set modes +Z (for an SSL connection) and +i (for being invisible to normal users unless they’re on a channel you’re on) on yourself

Register an account

  1. At the bottom of the main window is a text-entry line where you should type the following:
    1. /query nickserv
    2. register password email-address
    3. /sasl set freenode normal-nickname password PLAIN

Verify your e-mail address

  1. Check your e-mail for the verification e-mail, which will look like this:

    Subject: freenode Nickname Registration
    From: freenode automailer
    Olathe,

    In order to complete your registration, you must send the following command on IRC:
    /msg NickServ VERIFY REGISTER Olathe qzxqzxqzxqzx

    Thank you for registering your nickname on the freenode IRC network!

    Thank you for your interest in the freenode IRC network.

    This email was sent due to a command from Olathe[~Olathe@wifi.olathe] at Wed, 23 Oct 2013 22:19:00 +0000.
    If this message is spam, please contact support@freenode.net with a full copy.

  2. Copy and paste the entire /msg line from the e-mail you received (not from this page) into the same place you just registered your freenode account (the /query nickserv section you opened in XChat)

Change settings for your freenode account

  1. Type the following into the same place you just pasted the registration verification (the /query nickserv section you opened in XChat):
    1. set enforce on
    2. set hidemail on
    3. set private on
    4. /nick second-choice-nickname
    5. group
    6. /nick third-choice-nickname
    7. group

Set up Tor

Skip this section if you don’t want to use Tor!

  1. Type the following into the same place you just changed your freenode account settings (the /query nickserv section you opened in XChat):
    1. /set irc_hide_version ON
    2. /ignore * CTCP DCC

    tor-commands

  2. Press Ctrl-Alt-T to open a terminal window, and type the following:
    sudo apt-key adv --recv-keys --keyserver keyserver.ubuntu.com 886DDD89
    sudo add-apt-repository "deb http://deb.torproject.org/torproject.org $(lsb_release -s -c) main"
    sudo apt-get install -y deb.torproject.org-keyring
    sudo apt-get install -y tor
    exit
    
  3. Go to XChat’s Settings menu, Preferences
    1. Switch to the Interface section, Input box subsection and, under Nick Completion, fill out Nick completion suffix with :completion-setup
    2. Switch to the Chatting section, General subsection and erase all Default Messagesmessages-setup
    3. Switch to the Network section, Network setup subsection and do the following:
      1. Check next to Use Authentication (HTTP or Socks5 only)
      2. Fill out the following:
        • Hostname: 127.0.0.1
        • Port: 9050
        • Type: Socks5
        • Use proxy for: All connections
        • Username: XChat
        • Password: XChat

        network-setup

    4. Switch to the Network section, File transfers subsection
      1. Under Files and Directories, change Auto accept file offers to No
      2. Under Network Settings, change DCC IP address to 127.0.0.1dcc-setup
    5. Click OK
  4. Go to the Settings menu, Advanced submenu, CTCP Replies
    1. Repeatedly click Delete until all CTCP replies are gonectcp-setup
    2. Click Save
  5. Go to the XChat menu, Network List...
    1. Under Networks, choose FreeNode, and click Edit...
      1. Click on irc.freenode.net/7000, change it to p4fsi4ockecnea7l.onion/7000, and press enter
      2. Click Add, click on newserver/6667, change it to lgttsalmpw3qo4no.onion/7000, and press enter
      3. Click Add, click on newserver/6667, change it to 5jebommkgbfl6agc.onion/7000, and press enter
      4. Click Add, click on newserver/6667, change it to lbkwyb2csfcgoxwa.onion/7000, and press enter
      5. Uncheck Connect to selected server only
      6. Click Close

Store SASL password securely

  1. Quit XChat completely
  2. Press Ctrl-Alt-T to open a terminal window, and type the following:
    chmod 600 ~/.xchat2/*sasl*
    exit
    
  3. Start XChat by going to the Ubuntu application menu, Internet submenu, XChat IRC
  4. Make sure it connects to freenode, that you are set mode +Z, and that you do not see the following message:

    This nickname is registered. Please choose a different nickname, or identify via /msg NickServ identify <password>.

Get a cloak

  1. Type the following into XChat’s text-entry line:
    1. /join #freenode
      • If you set up Tor:
        Can I please get an unaffiliated cloak for when I'm not on Tor?
      • If you didn’t set up Tor:
        Can I please get an unaffiliated cloak?

      unaffiliated-cloak

  2. Wait for someone to give you a cloak; in the rare case that no one responds, try asking again in 10 minutes
  3. Once you get a cloak, thank the person who gave it to you and quit XChat completely

Check that everything is set up properly

  1. Start XChat by going to the Ubuntu application menu, Internet submenu, XChat IRC
  2. In XChat, type:
    1. /query nickserv
    2. info normal-nickname
  3. Ensure that your account information looks like the above
  4. If everything is set up properly, you’re done! If not, you can type /join #freenode and ask for help there

Read about how to use OTR chat

It’s important to understand that, though it’s unlikely they do so, it’s possible for some freenode administrators to view private conversations (in /query other-person's-nickname windows). If you use it properly, OTR encrypts these conversations so that only the two participants can read them.

The creator of the XChat OTR plugin has created some instructions, which you should read.

Posted in Ubuntu | Leave a comment

How to set up a minimalistic Lubuntu in VirtualBox

Set up the virtual machine

  1. Get the latest amd64 Lubuntu installer ISO.
  2. Get the latest amd64 Ubuntu mini-installer ISO.
  3. Create a Linux, Ubuntu (64 bit) virtual machine with no drive.
  4. In the virtual machine’s settings, create and attach a new 20 GB hard drive (main drive) and a new 4 GB hard drive (swap), then set up the hardware as you wish.

Prepare the drives

  1. Attach the Lubuntu installer ISO.
  2. Boot the virtual machine.
  3. Select Try Lubuntu without installing.
  4. Go to the Applications menu (you may have to scroll down), System Tools, GParted.
  5. Device menu, Create Partition Table..., Apply.
  6. Right click on unallocated, New, File system is ext4 (or whatever the latest standard is), Add.
  7. Edit menu, Apply All Operations, Apply.
  8. Right click on /dev/sda1, Manage Flags, check boot, Close.
  9. Switch from /dev/sda to /dev/sdb.
  10. Device menu, Create Partition Table..., Apply.
  11. Right click on unallocated, New, File system is linux-swap, Label is swap, Add.
  12. Edit menu, Apply All Operations, Apply.
  13. Close GParted.
  14. Go to the Applications menu, Accessories, LXTerminal, and run the following commands:
    sudo -i
    apt-get install zerofree
    zerofree -v /dev/sda1
    poweroff
    
  15. Wait 15 seconds and close the running virtual machine (choose Power off the machine).
  16. Open the virtual machine’s settings, detach the 4 GB drive, and click OK.
  17. File, Virtual Media Manager..., right click on the 4 GB drive, Modify..., Immutable, OK, Close.
  18. Open the virtual machine’s settings, reattach the 4 GB drive, and click OK.
  19. Open a terminal, switch to the directory with the virtual drives, and run the following on both drives:
    VBoxManage modifyhd --compact "[name of virtual drive].vdi"
    
  20. You now have two formatted drives. The one used for swap is immutable, which means that the drive will be restored to its current pristine state every time the virtual machine is rebooted.

Install Ubuntu base

  1. Attach the Ubuntu mini-installer ISO and boot the virtual machine.
  2. Choose Command-line install.
  3. Answer the prompts.
  4. When the Partition disks screen comes up:
    1. Choose the Manual partitioning method.
    2. For the 21.5 GB partition, use the following settings and then choose Done setting up the partition:
      Use as: Ext4 journaling file system
      Format the partition: no, keep existing data
      Mount point: /
      Mount options: defaults
      Bootable flag: on
      
    3. Go to Finish partitioning and write changes to disk and press enter.
    4. Choose No to not return to the partitioner.
    5. Choose Yes to write the changes.
  5. Make sure to install GRUB bootloader to the master boot record when it asks later on.
  6. When the installer returns to the original menu (with Command-line install), turn off the virtual machine.
  7. Detach the ISO.
  8. Start the virtual machine.
  9. Log in using the username and password you chose when installing Ubuntu base.
  10. Run the following commands:
    sudo rm -rf /tmp/*; sudo mount -t tmpfs tmpfs /tmp -o size=2G,mode=1777
    sudo -i
    nano /etc/fstab
    
  11. Add the following line to the bottom of the file, double-check that you entered it correctly, then press Ctrl-O, Enter, Ctrl-X:
    tmpfs /tmp tmpfs size=2G,mode=1777 0 0
    
  12. Run the following commands:
    apt-get update
    apt-get install -y virtualbox-guest-utils
    poweroff
    
  13. You now have a minimal install of Ubuntu.

Install Lubuntu

  1. Start the virtual machine (with no attached CDs).
  2. Log in using the username and password you chose when installing Ubuntu base.
  3. Run the following commands:
    sudo -i
    echo -e \\n# VirtualBox has no SMBus\\nblacklist i2c_piix4>> /etc/modprobe.d/blacklist.conf
    apt-get purge -y fuse geoip-database krb5-locales os-prober ppp
    apt-get install -y software-properties-common
    add-apt-repository -y ppa:lubuntu-dev/non-official-apps
    apt-get update
    apt-get install -y --auto-remove --no-install-recommends lubuntu-core
    echo -e \#\!/bin/sh\\n\\nrm -f /tmp/.menu-cached-:0-\${USER}\\n/usr/bin/lxpanel \${1+\"\$@\"}> /usr/local/bin/lxpanel
    chmod a+x /usr/local/bin/lxpanel
    sed -i '/xscreensaver/d' /etc/xdg/lxsession/Lubuntu/autostart
    sed -i '/xfce4-power-manager/d' /etc/xdg/lxsession/Lubuntu/autostart
    apt-get install -y gksu policykit-1-gnome lxtask lxterminal menulibre
    echo Hidden=true>> /usr/share/applications/debian-xterm.desktop
    echo Hidden=true>> /usr/share/applications/debian-uxterm.desktop
    
  4. If your virtual machine won’t have much RAM assigned to it:
    apt-get install -y zram-config
    
  5. If you’d like a lightweight image viewer:
    apt-get install -y viewnior
    
  6. If you’d like a lightweight web browser:
    apt-get install -y xombrero
    
  7. If you’d like very lightweight graphical effects like shadows under windows and see-through titlebars:
    apt-get install -y compton
    echo @compton -bcCGfe 0.8 -I 1 -O 0.06 --sw-opti>> /etc/xdg/lxsession/Lubuntu/autostart
    
  8. If you’d like Oracle’s version of Java (change java7 to another version if you’d like):
    add-apt-repository -y ppa:webupd8team/java
    apt-get update
    apt-get install -y oracle-java7-installer
    find /var/cache/ -name jdk-*.tar.gz -delete
    
  9. If you’d like sudo to work without a password:
    sed -i 's/^%sudo\tALL=(ALL:ALL) ALL$/%sudo\tALL=(ALL:ALL) NOPASSWD: ALL/' /etc/sudoers
    
  10. If you’d like the user to have a blank password (replace username with the actual username):
    sed -i 's/^\(username:\)[^:]*/\1U6aMy0wojraho/' /etc/shadow
    
  11. If you’d like to disable guest logins:
    /usr/lib/lightdm/lightdm-set-defaults -l false
    
  12. If you’d like the system to automatically log in as this user (replace username with the actual username):
    /usr/lib/lightdm/lightdm-set-defaults -a username
    
  13. Use apt-get to install any other software you’d like.
  14. Wait for the virtual machine to restart with Lubuntu running.
  15. Choose Lubuntu as the session type.
  16. Log in as the user you created.
  17. Set the system up as you wish.
  18. If you installed Oracle’s version of Java, you may wish to turn off the browser plugin (this can be done for all browsers in the Java control panel).
  19. Go to the Applications menu, Accessories, LXTerminal, and run the following commands:
    sudo -i
    apt-get update
    apt-get -y dist-upgrade
    apt-get autoremove --purge
    apt-get clean
    updatedb
    poweroff
    
  20. You now have a Lubuntu system set up as you wish.

Prepare a backup/distribution archive

  1. File, Virtual Media Manager..., right click on the 20 GB drive, Copy..., Next >, VDI (VirtualBox Disk Image), Next >, Dynamically allocated, Next >, Copy, Close.
  2. Attach the copy you just made.
  3. Attach the Lubuntu installer ISO.
  4. Boot the virtual machine.
  5. Select Try Lubuntu without installing.
  6. Go to the Applications menu (you may have to scroll down), Accessories, LXTerminal, and run the following commands:
    sudo -i
    mkdir /mnt/old
    mount -o rw /dev/sdc1 /mnt/old
    cd /mnt/old
    rm -rf tmp/* tmp/.* var/log/* var/log/.*
    for i in .aptitude .bash_history .mysql_history .dbus .gconf '.xsession-errors*'; do find -name "$i" -exec rm -rf {} +; done
    find -print0 | sort -z | tar vvcf contents.tar --no-recursion --null -T -
    mkfs.ext4 -U `blkid -o value -s UUID /dev/sda1` /dev/sda1
    mkdir /mnt/new
    mount -o rw /dev/sda1 /mnt/new
    cd /mnt/new
    tar vvxf /mnt/old/contents.tar
    cd /
    umount /dev/sda1
    apt-get install zerofree
    zerofree -v /dev/sda1
    poweroff
    
  7. Wait 15 seconds and close the running virtual machine (choose Power off the machine).
  8. File, Virtual Media Manager..., do the following:
    1. Right click on the copy of the 20 GB drive, Release, Release, right click on the copy of the 20 GB drive, Remove, Remove, Delete.
    2. Click the triangle next to the 4 GB drive to expand it, right click on the strangely-named drive that shows up below it, Release, Release, right click on the strangely-named drive, Remove, Remove, Delete.
    3. Switch to Optical disks tab, and do the following with each optical disk: right click on the disk, Remove, Remove.
    4. Click Close.
  9. Reattach the 4 GB drive.
  10. Open a terminal, switch to the directory with the virtual drives, and run the following (filling in the name of the 20 GB drive and virtual machine):
    VBoxManage modifyhd --compact "[name of 20 GB virtual drive].vdi"
    rm -rf Logs/*
    rm -f *.vbox-prev
    cd ..
    find "[name of virtual machine]" -print0 | sort -z | tar vvcf machine.tar --owner=0 --group=0 --no-recursion --null -T -
    xz -vvz --lzma2=dict=255MiB,lc=3,lp=1,pb=2,mode=normal,nice=273,mf=bt4,depth=2000 --check=sha256 machine.tar
    
  11. Now you have a VirtualBox image (machine.tar.xz) with customized minimalistic Lubuntu that you can distribute to others or use to get back to a pristine state.
Posted in Ubuntu | Leave a comment

Unsigned comparisons in Java

You can perform unsigned comparisons of longs without using horribly inefficient BigIntegers. After testing a few ideas I came up with against some code by Tamutnefret of Freenode’s ##java, I found his code was fastest, so I’ve based the code below on it.

Unsigned comparisons to another variable

Here are efficient ways to do all six unsigned comparisons:

boolean aLTb = (a <  b) ^ (a < 0L) ^ (b < 0L);
boolean aLEb = (a <= b) ^ (a < 0L) ^ (b < 0L);
boolean aEQb = (a == b);
boolean aNEb = (a != b);
boolean aGEb = (a >= b) ^ (a < 0L) ^ (b < 0L);
boolean aGTb = (a >  b) ^ (a < 0L) ^ (b < 0L);

Unsigned comparisons to constants

If you’re comparing to a constant, here are even more efficient ways to do it.

Comparing to zero:

boolean aLTzero = false;
boolean aLEzero = (a == 0L);
boolean aEQzero = (a == 0L);
boolean aNEzero = (a != 0L);
boolean aGEzero = true;
boolean aGTzero = (a != 0L);

Comparing to one:

boolean aLTone = (a == 0L);
boolean aLEone = (a <= 1L) ^ (a < 0L);
boolean aEQone = (a == 1L);
boolean aNEone = (a != 1L);
boolean aGEone = (a != 0L);
boolean aGTone = (a > 1L) ^ (a < 0L);

Comparing to anything from two to 263 – 2:

boolean aLTposConst = (a <= posConstMinus1) ^ (a < 0L);
boolean aLEposConst = (a <= posConst)       ^ (a < 0L);
boolean aEQposConst = (a == posConst);
boolean aNEposConst = (a != posConst);
boolean aGEposConst = (a >  posConstMinus1) ^ (a < 0L);
boolean aGTposConst = (a >  posConst)       ^ (a < 0L);

Comparing to 263 – 1:

boolean aLT2to63minus1 = (a >= 0L) ^ (a == Long.MAX_VALUE);
boolean aLE2to63minus1 = (a >= 0L);
boolean aEQ2to63minus1 = (a == Long.MAX_VALUE);
boolean aNE2to63minus1 = (a != Long.MAX_VALUE);
boolean aGE2to63minus1 = (a < 0L) ^ (a == Long.MAX_VALUE);
boolean aGT2to63minus1 = (a < 0L);

Comparing to 263:

boolean aLT2to63 = (a >= 0L);
boolean aLE2to63 = (a >= 0L) ^ (a == Long.MIN_VALUE);
boolean aEQ2to63 = (a == Long.MIN_VALUE);
boolean aNE2to63 = (a != Long.MIN_VALUE);
boolean aGE2to63 = (a <  0L);
boolean aGT2to63 = (a <  0L) ^ (a == Long.MIN_VALUE);

Comparing to anything from 263 + 1 to 264 – 3 (make sure you write the constant in signed form):

boolean aLTnegConst = (a <  negConst) ^ (a >= 0L);
boolean aLEnegConst = (a <= negConst) ^ (a >= 0L);
boolean aEQnegConst = (a == negConst);
boolean aNEnegConst = (a != negConst);
boolean aGEnegConst = (a >= negConst) ^ (a >= 0L);
boolean aGTnegConst = (a >  negConst) ^ (a >= 0L);

Comparing to 264 – 2:

boolean aLT2to64minus2 = (a != -1L) && (a != -2L);
boolean aLE2to64minus2 = (a != -1L);
boolean aEQ2to64minus2 = (a == -2L);
boolean aNE2to64minus2 = (a != -2L);
boolean aGE2to64minus2 = (a == -1L) || (a == -2L);
boolean aGT2to64minus2 = (a == -1L);

Comparing to 264 – 1:

boolean aLT2to64minus1 = (a != -1L);
boolean aLE2to64minus1 = true;
boolean aEQ2to64minus1 = (a == -1L);
boolean aNE2to64minus1 = (a != -1L);
boolean aGE2to64minus1 = (a == -1L);
boolean aGT2to64minus1 = false;
Posted in Java, Optimization | Leave a comment

How to compute 64-bit integer square roots very quickly

From an article section I’ve been working on for the past few days at code codex,

The int version simply casts the result of StrictMath.sqrt to an int, giving us full hardware speed.

The long version uses a trick by Programmer Olathe to get exact results from StrictMath.sqrt even though doubles only have 52 bits precision: StrictMath.sqrt is guaranteed to give the exact result or the exact result plus one. This gets us very near full hardware speed.

longs have 64 bits and Java keeps only the most significant 52 bits when casting to double, so you can lose up to 12 bits.

If the input uses more than 52 bits, the distance between squares is at least (226)2 – (226 – 1)2 = 227 – 1. So, even if you lose the maximum of 12 bits, the distance between perfect squares is much greater than a 12-bit number, and so there cannot be more than one perfect square per “zone” of longs that cast to the same double.

This leaves two possibilities.

  1. There are no perfect squares in the zone, in which case the integer part of sqrt will correspond to the next lowest perfect square, which is great.
  2. There is only one perfect square in the zone, in which case the integer part of sqrt will correspond to that perfect square, and that’s either great or, if our input is less than that perfect square, we simply need to subtract one.

The BigInteger version uses the long version to quickly get the square root of the most significant 64 bits, and then it fills in the remaining bits of the result from most to least significant, checking whether putting a 1 in that place would exceed the input and using 0 instead if that’s the case. It is designed to minimize BigInteger object creation, creating less than two intermediate BigIntegers per output bit.

public class MathTools {
  // floorSqrt :: unsigned long -> unsigned int
  // Gives the exact floor of the square root of x, treated as unsigned.
  public static final int floorSqrt(final int  x) { return (int) StrictMath.sqrt(x & 0xffffffffL); }
  public static final int floorSqrt(final long x) {
    if ((x & 0xfff0000000000000L) == 0L) return (int) StrictMath.sqrt(x);
    final long result = (long) StrictMath.sqrt(2.0d*(x >>> 1));
    return result*result - x > 0L ? (int) result - 1 : (int) result;
  }
}
Posted in Java, Optimization | Leave a comment

Showing the source code view of a Java String

public class InspectString {
  public static String inspect(final String str) {
    String result = "\"";
    final char[] chs = str.toCharArray();
    for (int i = 0; i < chs.length; i++) {
      final char ch = chs[i];
      if      (ch >= 128) result += String.format("\\u%04x", (int) ch);
      else if (ch == '"') result += "\\\"";
      else if (ch >=  32) result += ch;
      else switch (ch) {
        case '\b':        result += "\\b"; break;
        case '\f':        result += "\\f"; break;
        case '\n':        result += "\\n"; break;
        case '\r':        result += "\\r"; break;
        case '\t':        result += "\\t"; break;
        default:        if (i == chs.length - 1)
                          result += String.format("\\%o", (int) ch);
                        else {
                          final char nextCh = chs[i + 1];
                          result += String.format((nextCh >= '0' && nextCh <= '9') ? "\\%03o" : "\\%o", (int) ch);
                        }
      }
    }
    result += "\"";
    return result;
  }
  
  public static final void main(final String[] args) {
    System.out.println(inspect("zomg\0\u28af!!! !!!.123\"'\n\n\t\r\b\1\0133\013\f"));
  }
}
Posted in Java | Leave a comment

HOWTO: Install irssi in full screen, translucent glory on Ubuntu 10.10

I recently switched to Ubuntu 10.10 from Windows XP and was trying to get irssi running in gnome-terminal in a certain way:

  • Full screen so that it takes up an entire workspace.
  • Translucent background so that I can see my nice Digital Blasphemy wallpaper.

With gnome-terminal maximized, I got an ugly window title bar that I didn’t want. With gnome-terminal full screen, I couldn’t see what I was typing, since the bottom line of the terminal window is right over my task switching Gnome panel (the thing at the bottom of the screen that lets you switch between all the windows that are open) and so I had the text I was typing mixed up visually with the names of open windows.

The solution on Ubuntu 10.10 is pretty simple if you’re pretty familiar with Ubuntu: you maximize the irssi window, set its Gtk+ role to irssi by using gnome-terminal‘s --role option, and set up Compiz to not decorate windows with that role.

If you have no idea what that means, no problem. Here’s a full set of installation instructions.

Installation instructions

Here’s how to install irssi from scratch so that it runs full screen and translucent.

  1. Install irssi
    $ sudo apt-get install irssi irssi-scripts
    $ sudo mkdir -pv /usr/local/share/icons
    $ sudo wget --output-document=/usr/local/share/icons/irssi-icon.png "http://svn.irssi.org/cgi-bin/viewvc.cgi/irssi/trunk/irssi-icon.png?view=co&root=irssi"
    
  2. If you plan on using Freenode, make your NickServ password more secure by encrypting your session (to foil eavesdropping) and automatically logging in (to keep from accidentally telling an entire channel your password when you forget the slash)
  3. Start Appearance preferences (System menu, Preferences submenu, Appearance)
  4. Go to the Visual effects tab
  5. Choose Normal or Extra
  6. Press the Close button

  7. Install CompizConfig Settings Manager
    $ sudo apt-get install compizconfig-settings-manager
    
  8. Start CompizConfig Settings Manager (System menu, Preferences submenu, CompizConfig Settings Manager)
  9. Turn on the Regex Matching plugin
  10. Turn on the Window Decoration plugin
  11. In Window Decoration settings, change both Decoration windows and Shadow windows from any to !role=irssi
  12. Close CompizConfig Settings Manager

  13. Right click on the Applications menu and choose Edit Menus
  14. Choose Internet on the left side
  15. Press the New Item button on the right side
  16. Fill in the Launcher Properties popup window as follows
    Icon:      /usr/local/share/icons/irssi-icon.png
    Type:      Application
    Name:      irssi
    Command:   gnome-terminal --zoom=1.0 '--title=irssi' --profile=irssi --maximize --hide-menubar --role=irssi -e irssi
    Comment:   Chat with irssi
    
  17. Press the OK button
  18. Press the Close button of the menu editor window

  19. Switch to an empty workspace
  20. Start up irssi (Applications menu, Internet submenu, irssi)
  21. Right click on the irssi window and choose Show Menubar
  22. Click the File menu and choose New Profile...
  23. For Profile name, type irssi and press the Create button
  24. Go to the Title and Command tab and uncheck Update login records when command is launched and, for When command exits, choose Exit the terminal
  25. Go to the Background tab, choose Transparent background and move the slider just below that to get the translucency of the open irssi window as you like it
  26. Go to the Scrolling tab and, for Scrollbar is, choose Disabled and check Unlimited
  27. Click the Close button
  28. Into the irssi window, type /quit and press enter, closing the window if it doesn’t close automatically

  29. Start up irssi from the Applications menu again
  30. If half a line or so is wasted at the bottom of the terminal window like it was with mine, open the Applications menu editor again and repeat the following until that’s fixed
    1. Quit irssi (type /quit and press enter)
    2. Edit the settings for irssi
    3. Tune gnome-terminal‘s --zoom option a bit (--zoom=0.9 worked for my 1280×960 screen with one Gnome panel at the bottom)
    4. Press the Close button to save your changes
    5. Restart irssi from the Applications menu to check your new settings
Posted in Ubuntu | Leave a comment

Monads: semantics for subroutines

Monads are fairly simple to understand. Each Monad specifies a different way to execute an imperative-style subroutine.

Monads tell what happens between statements
Monads are sometimes called “executable semicolons” because they control what nice automation happens between each and every line of a subroutine. Getting a new useful effect is usually the main purpose for making a new Monad. A few examples :

  • Whenever a line in one of your Maybe subroutines produces Nothing, the entire subroutine will stop and produce Nothing, which saves you from the Java hell of writing a bunch of x = ...; if (x == null) return null; y = g(x); if (y == null) return null; ... for each and every operation that might produce null.
  • State makes sure to preserve the data stored in it.

These special effects are all programmed into each Monad‘s (>>=) function.

Subroutines produce values
Subroutines will do something useful and, at the end, produce a value that can be used by other subroutines that use the same Monad‘s semantics. A do block will produce whatever its last line happens to produce, so if the last line of your do block produces a line from stdin, your do block will produce a line from stdin.

getThirdLine :: IO String
getThirdLine = do getLine
                  getLine
                  -- Our subroutine will produce whatever the last line produces.
                  -- "getLine" produces the next line from stdin.
                  -- Our subroutine will produce the next line from stdin.
                  getLine

To make certain things easier, return is a subroutine that does nothing but produce the value you give to it.

getLastCharOfThirdLine :: IO Char
getLastCharOfThirdLine = do -- "<-" puts the value produced
                            -- by the subroutine on the right
                            -- into the variable on the left.
                            thirdLine <- getThirdLine
                            -- Our subroutine will produce whatever the last line produces.
                            -- "return" is a subroutine that simply produces its argument.
                            -- Our subroutine will produce "last thirdLine".
                            return (last thirdLine)

In Java or C, you may have seen subroutines that have the return type void, which means they don’t produce anything. In Haskell, the idiom is to produce (), using return () if necessary. You’ll see subroutines that produce () quite a bit, particularly if the sole purpose is to cause a side effect (like writing to a file in IO or overwriting the state in State).

Monads are sometimes bundled with special subroutines. IO has a bunch of nice file-handling subroutines. State lets you get the data it now holds and put a replacement.

Domain-specific languages
Because of their flexibility, Monads are used to create domain-specific languages (DSLs) in Haskell. For instance, the programming language BASIC was implemented as a Monad.

Posted in Haskell monads | Leave a comment

The List, ListState, and Player monads

If we want to use the nice, imperative do blocks of Haskell to produce a lazy list from another lazy list, we have a few options: the List monad, the ListState monad, and the Player monad.

The List monad :

  • is essentially [a] -> [b], allowing each differing lengths.
  • runs your do block once for the each element in the list, preventing you from keeping any state based on previous elements.
  • x <- xs takes an arbitrary input element.
  • [a, b, c] squeezes a, b, and c into the list where the input element used to be.

An example that outputs a number that number of times ([0, 1, 2, 3][1, 2, 2, 3, 3, 3]) :

nTimes :: Integral a => [a] -> [a]
nTimes ns = do n <- ns
               map (const n) [1..n]

The definition of the List monad :

instance Monad [] where
  return x = [x]
  []     >>= _ = []
  (x:xs) >>= f = f x ++ (xs >>= f)

The ListState monad :

  • is essentially [a] -> [b], allowing each differing lengths.
  • runs your do block once for the entire list, so that you can easily keep state based on previous elements.
  • x <- getNext takes the next input element, advancing the input list.
  • putNext x gives the next output element, advancing the output list.

This example shows how state allows you to go beyond the List monad. You can flip pairs of elements ([1, 2, 3, 4][2, 1, 4, 3]) :

flipPairs :: [a] -> [a]
flipPairs = processList . forever $ do x <- getNext
                                       y <- getNext
                                       putNext y
                                       putNext x

This example shows how running once for the whole list rather than once per element allows you to go beyond the List monad. You can flip the first pair and drop the rest of the list ([1, 2, 3, 4][2, 1]) :

firstPairFlipped :: [a] -> [a]
firstPairFlipped = processList $ do x <- getNext
                                    y <- getNext
                                    putNext y
                                    putNext x

The definition of the ListState monad :

module ListState  (processList, getNext, putNext) where

import Data.Maybe  (isNothing)

newtype ListState a b r = ListState { runListState :: Maybe [a] -> [b] -> (r, Maybe [a], [b]) }

-- |Process this list and return the new list.
processList :: ListState a b r -> [a] -> [b]
processList f xs = let (_, _, ys) = runListState f (Just xs) []
                   in ys

-- Make a custom welding of state and reverse state (http://lukepalmer.wordpress.com/2008/08/10/mindfuck-the-reverse-state-monad/) monads.
instance Monad (ListState a b) where
  return x = ListState $ \fwd rev -> (x, fwd, rev)
  m >>= f  = ListState g
    where
      g xs ys = let (a, xs', ys'') = runListState m xs ys'
                    (b, xs'', ys') = if isNothing xs'
                        then (undefined, xs', ys)
                        else runListState (f a) xs' ys
                in (b, xs'', ys'')

getNext :: ListState a b a
getNext = ListState f
  where
    f (Just [])     ys = (undefined, Nothing, ys)
    f (Just (x:xs)) ys = (x,         Just xs, ys)

putNext :: b -> ListState a b ()
putNext y = ListState $ \xs ys -> ((), xs, y:ys)

The Player monad :

  • is essentially [a] -> [[b]], where the [a] is the same length as the [[b]].
  • runs your do block once for the entire list, so that you can easily keep state based on previous elements.
  • x <- getState repeatedly takes the current input element without advancing.
  • move x adds an item to the current output element without advancing.
  • endTurn advances the input and output lists.

If you’re writing the code for a bot that plays a game, the Player monad is quite nice. The monad will take a lazy list of each turn’s starting information and immediately give you a lazy list of each turn’s moves for that bot. The bot sees this turn’s starting information, gives move after move, tells when it’s finished with the turn, and can keep between-turn state.

module Player  (playWith, getState, move, endTurn) where

import Data.Maybe  (isNothing)

newtype Player a b r = Player { runPlayer :: (a, Maybe [a]) -> ([b], [[b]]) -> (r, (a, Maybe [a]), ([b], [[b]])) }

-- |Play the game with this player and return a list of each turn's moves.
playWith :: Player a b r -> [a] -> [b]
playWith _ []     = []
playWith f (x:xs) = let (_, _, (_, ys)) = runPlayer f (x, Just xs) ([], [])
                in ys

-- Make a custom welding of state and reverse state (http://lukepalmer.wordpress.com/2008/08/10/mindfuck-the-reverse-state-monad/) monads.
instance Monad (Player a b) where
  return x = Player $ \fwd rev -> (x, fwd, rev)
  m >>= f  = Player g
    where
      g xs ys = let (a, xs', ys'') = runPlayer m xs ys'
                    (b, xs'', ys') = if isNothing . snd $ xs'
                        then (undefined, xs', ys)
                        else runPlayer (f a) xs' ys
                in (b, xs'', ys'')

getState :: Player a b a
getState = Player $ \xxs@(x, _) yys = (x, xxs, yys)

move :: b -> Player a b ()
move z = Player $ \xxs (y, ys) -> ((), xxs, (z:y, ys))

endTurn :: Player a b ()
endTurn = Player g
  where
    g (_, Just [])     (y, ys) = ((), (undefined, Nothing), (undefined, y:ys))
    g (_, Just (x:xs)) (y, ys) = ((), (x,         Just xs), ([],        y:ys))
Posted in Haskell monads | Leave a comment