Monthly Archives: February 2013

Hashing

Non-cryptographic hash functions

Leave a comment

Here is a collection of all the “good” non-cryptographic hash functions that I am aware of. Also

Hash function page from Wikipedia.

Bob Jenkins

http://burtleburtle.net/bob/hash/

1997 – lookup8 (64-bit)

2006 – lookup3 (32-bit and 64-bit)

Also see SpookyHash

CityHash

The CityHash family of hash functions (32-bit through 128-bit).

MurmurHash

MurmurHash2- deprecated.

MurmurHash3 and SMHasher (SMHasher is a test suite).

Test statistics from 2008.

FNV

FNV Hash – only use FNV-1a.

Miscellaneous

Old Hash Functions page from 1990 era.

Hash Functions page by Paul Hsieh, 2008.

Which hashing algorithm is best for uniqueness and speed from the Programmers StackExchange.

Hash functions: an empirical comparison from strchr.com.

xxhash on code.google.com

Hash functions page from Bret Mulvey, 2007

Creating a Fast Hash Function

 

Uncategorized

Best format for parameter expansion?

Leave a comment

Many languages and document systems have a way to have formal variables in strings replaced by specific instance values. The dominant practice is to use braces, with some prefix character, often $. These are the most common, in order

  • ${PARAMETER}
  • {PARAMETER}
  • #{PARAMETER}

Other widely-used formats (where widely-used is by usage)

  • $PARAMETER
  • $(PARAMETER)

Some systems generalize PARAMETER to include arbitrary expressions, some have separate syntax for variable interpolation versus expression interpolation.

There is a Wikipedia page for String Interpolation, but it is incomplete/misleading. Maybe I should update it.

Suggestion for a new system? Use ${EXPRESSION} and allow at least simple variables, but preferably full expressions.

Perl

Perl calls it “interpolation” when you put variables inside strings. Perl allows all variable types to be expanded. In a string, it’s common practice to surround the variable name with braces to better disambiguate variable names from surrounding text.

my $name = "Brian";
my $action = "jump";
print "$name ${action}s\n";
# output: Brian jumps

It’s called interpolation more when it is about inserting arrays into strings, because array elements are as a convenience separated by spaces.

Many configuration systems (including Puppet and Nagios) have Perl-like syntax for string interpolation. PHP deviates a bit because it uses $PARAMETER for simple cases, and {$EXPRESSION} for more complicated ones.

Python

Python doesn’t have implicit expansion, but it has several systems for doing explicit expansion.

The format() function uses {PARAMETER} syntax.

>>> d = { 'vars': "variables", 'example': "example" }
>>> s = "This is an {example} with {vars}"
>>> s.format(**d)
'This is an example with variables'

There is a Template module that uses a $PARAMETER syntax

>>> from string import Template
>>> t = Template("This is an $example with $vars")
>>> t.substitute({ 'example': "example", 'vars': "variables"})
'This is an example with variables'

python multiline string for variables from StackOverflow

Ruby

Ruby has generalized interpolation of expressions into strings with #{EXPRESSION}, where the expression can be as simple as a single variable, or as complicated as you want.

Bash

Bash share’s Perls syntax for strings (or is it that Perl used Bash’s syntax?).

set WORD=jump
echo "The plural of $WORD is most likely ${WORD}s"
# output: The plural of jump is most likely jumps

Bash has a lot of decoration to parameter substitution driven by the fact that there is no higher-level language backing things up, so it has to have decoration for indirection, case change, substring, search/replace and so on; things that would all be done outside of parameter expansion in other systems.

This syntax probably goes back to the original /bin/sh shell, because the fundamentals of this are shared by csh/tcsh, and some other shells.

Bash parameter expansion syntax

zsh

The zsh shell does parameter expansion as $PARAMETER or ${PARAMETER}, and introduces a new syntax to do function expansion – $(func) calls func and inserts its output as text.

zsh is very similar to ksh.

A User’s Guide to the Z-Shell

Dart

Dart, Google’s replacement for Javascript, uses $PARAMETER for simple variables, and ${EXPRESSION} for arbitrary expressions. If EXPRESSION is a variable, then the toString() method is automatically called on that variable.

Dart String Interpolation

Microsoft

Batch files use %PARAMETER% for variable expansion, and have decorators for substring and substitution, except that batch files do immediate substitution, not delayed substitution (e.g. changing a variable at “run time”). There is special syntax to add delayed substitution, bringing it more in line with other systems; these are written as !PARAMETER!. Presumably this was due to fears of existing batch files depending on immediate substitution.

Microsoft tends to like $(PARAMETER) for its variable expansion syntax in newer systems. This is used by Visual Studio and MSBuild, among other systems.

Build systems

Hand-constructing Visual Studio 2012 vcxproj

Leave a comment

Here is the simplest legal vcxproj that I could make.

<?xml version="1.0" encoding="utf-8"?>
<Project DefaultTargets="Build" ToolsVersion="4.0"
         xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
  <ItemGroup Label="ProjectConfigurations">
    <ProjectConfiguration Include="Debug|Win32">
      <Configuration>Debug</Configuration>
      <Platform>Win32</Platform>
    </ProjectConfiguration>
  </ItemGroup>
</Project>

The first line declares it as an XML file, with the body in UTF-8.

<?xml version="1.0" encoding="utf-8"?>

The root element of an MSBuild XML document is Project. I’m assuming that the ToolsVersion=”4.0″ refers to MSBuild 4.0.

<Project DefaultTargets="Build" ToolsVersion="4.0"
         xmlns="http://schemas.microsoft.com/developer/msbuild/2003">

Every vcxproj must have at least one project configuration. This is wrapped inside an ItemGroup element that has a label of “ProjectConfigurations”. There are only a few sub-elements of Project allowed.

  <ItemGroup Label="ProjectConfigurations">
    <ProjectConfiguration Include="Debug|Win32">
      <Configuration>Debug</Configuration>
      <Platform>Win32</Platform>
    </ProjectConfiguration>
  </ItemGroup>

You can have as many project configurations as you want, although the real variable is Configuration – you’re more limited on Platform, since MSBuild has to understand that platform.

This project file will actually open up in Visual Studio, or be parsed by MSBuild, but you need a few more elements before you have something useful. First, note that project XML files are written in a specific order, and parsed as they are written. The XML is not in a canonical order, so you can’t use a tree parser to read or write these.

First off, a lot of the behavior is inherited. There are some magic import lines to scatter throughout your project file. Let’s focus on those. Here they are in a group. (Note for expert users: I am ignoring the fact that project files try to inherit from a user directory – that’s an abomination, and you don’t want that in your project files).

...
  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.Default.props" />
...
  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.props" />
...
  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
...

All of these are found in your MSBuild folder, which for me is C:\Program Files (x86)\MSBuild\Microsoft.Cpp\v4.0\V110; your mileage may vary.

Microsoft.Cpp.Default.props handles some default settings; if you don’t specify Platform, then Platform=Win32; if you don’t specify a Configuration, then Configuration=Debug; and so on.

Microsoft.Cpp.props is a wrapper to import the proper platform props, which is “$(VCTargetsPath)\Platforms\$(Platform)\Microsoft.Cpp.$(Platform).props”, which simply turns around and imports “$(VCTargetsPath)\Microsoft.Cpp.Platform.props”. The layers are used by platforms like ARM to declare min platform versions. This eventually leads to files like Microsoft.Cpp.Win32.v110.props, which sets paths, and Microsoft.Cpp.Common.props, which sets the majority of the defaults.

Microsoft.Cpp.targets sets up a lot of the default scaffolding for building C++ projects. Or, to restate it, it sets up the project file to build C++ projects. It’s one of the final lines in your project file.

It would be interesting to draw out the map of what’s included here; I suspect there is some organizational method, but it’s not obvious at first glance.

Note that if you use Microsoft.Cpp.props, you will get what the system defaults to – for me, it actually defaults to v100, which is Visual Studio 2010. So you need a few lines before that include to set specific properties for the project. Strictly speaking, you only need to set the PlatformToolset to v110; everything else has a default.

  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'" Label="Configuration">
    <ConfigurationType>StaticLibrary</ConfigurationType>
    <UseDebugLibraries>true</UseDebugLibraries>
    <PlatformToolset>v110</PlatformToolset>
    <CharacterSet>Unicode</CharacterSet>
  </PropertyGroup>

Now, if you put all of this together, you’ll end up with a project file that opens in Visual Studio and could actually be used to add files to, build with, and etc. It’s still not a complete project file; if you compare against a wizard-generated one, you’ll see lots of extra settings. But it is complete and almost useful.

<?xml version="1.0" encoding="utf-8"?>
<Project DefaultTargets="Build" ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
  <ItemGroup Label="ProjectConfigurations">
    <ProjectConfiguration Include="Debug|Win32">
      <Configuration>Debug</Configuration>
      <Platform>Win32</Platform>
    </ProjectConfiguration>
  </ItemGroup>
  <PropertyGroup Label="Globals">
    <ProjectGuid>{FBEF15CB-6F54-49E3-853B-4238684902B8}</ProjectGuid>
    <Keyword>Win32Proj</Keyword>
    <RootNamespace>SHA1</RootNamespace>
  </PropertyGroup>
  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.Default.props" />
  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'" Label="Configuration">
    <ConfigurationType>StaticLibrary</ConfigurationType>
    <UseDebugLibraries>true</UseDebugLibraries>
    <PlatformToolset>v110</PlatformToolset>
    <CharacterSet>Unicode</CharacterSet>
  </PropertyGroup>
  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.props" />
  <Import Project="..\time-hash.lib.props" />
  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
</Project>

Why am I doing this? I need to construct good Visual Studio projects automatically, and I don’t want to create things based on copy/paste information.

Build systems

MSBuild

Leave a comment

Microsoft’s new way, so we must use it. It’s hopefully better than driving builds through an IDE with “devenv” invocations.

This is scattered bits while I try to put a coherent picture together.

Walkthrough: Using MSBuild

Walkthrough: Creating an MSBuild Project File from Scratch

MSBuild Targets

These are half-related.

Visual Studio project properties for multiple projects (from StackOverflow)

Using property sheets in Visual Studio 2010 (from StackOverflow)

How to: Add New Property Sheets to C++ Projects

Visual Studio and MSBuild

printf(“Hello MSBuild!\n”);

Converting to MSBuild

Response to the feature poll

Exploring the New MSBuild Features for Visual C++ 2010

 

R

R recipes

Leave a comment

Cumulative probability distribution graph

Assume data is in the first variable of the data frame tz

n <- length(tz$V1)
plot(sort(tz$V1), (1:n)/n, type="s")

This will plot a no-frills cumulative probability distribution graph.

Histogram

Assume data is in the first variable of the data frame tz

hist(tz$V1, nclass=60)

This will plot a histogram with 60 buckets. If you leave nclass off, then R will compute what it thinks a reasonable bucket count and bucket width are. Note that you can also supply a vector declaring the width of each bucket.