gistfile1.txt

== Pseudo-code for a new caps hash algorithm ==
- Not susceptible to trivial preimage attacks
- No escaping required
- Can be implemented efficiently
- Pseudo-code uses functional primitives, but easily translatable to non-functional languages (like C)
- No undefined edge cases, everything fully specified, including when attributes/elements are missing or duplicated
- 'ver' based on JSON-isque delimiters, using null byte '\0' as escape

- Possibly controversial aspects:
	- Concious decision to not fail on missing required elements/attributes
	- Concious decision to not check for duplicates (duplicate feature elements, etc)
	- Reason: Improves efficieny and simplifies implementation, with no practical loss

function hash(discoElement)
	featureElements = getFeatureElements(discoElement)
	identityElements = getIdentityElements(discoElement)
	discoExtensionElements = getDiscoExtensions(discoElement)

	features = sort(map(featureElements, |feature| return feature.getAttribute('var')))
	identities = sort(map(identityElements, |identity|
		return "\0{"
			+ identity.getAttribute('category') + "\0,"
			+ identity.getAttribute('type') + "\0,"
			+ identity.getAttribute('xml:lang') + "\0,"
			+ identity.getAttribute('name') + "\0}"
	))
	discoExtensions = sort(map(discoExtensionElements, |form|
		fieldElements = getFieldElements(form)
		formType = ""
		fields = sort(map(fieldElements, |field|
			fieldName = field.getAttribute('var')
			valueElements = getValueElements(field)
			if fieldName == "FORM_TYPE" and valueElements.length > 0 then
				formType = valueElements.firstItem.getText()
			end
			values = sort(map(valueElements, |value| value.getText()))
			return fieldName + "\0:\0{" + concat(values, "\0,") + "\0}"
		))
		return formType + "\0:\0{" + concat(fields, "\0,") + "\0}"
	))

	ver = "\0{" + concat(features, "\0,") + "\0}"
		+ "\0{" + concat(identities, "\0,") + "\0}"
		+ "\0{" + concat(discoExtensions, "\0,") + "\0}"

	return sha1(ver)
end

function hash
	- main algorithm; takes a disco element, returns a hex hash. 
function sort
	- Simple sorting of a string array; can be in-place.
function map
	- Given an array of elements, generates an array of strings, with one string from each element.
	- Syntax a bit ruby-ish. The second parameter is simply executed for each element to build the result array.
function concat
	- takes a string array 'array' and a string 'separator' as arguments, returns a string
	- result = ""; for (each string s in string array) { result = result + s + separator } return result;
function get*Elements
	- given an element, returns a list of all children of a specific type
function element.getText
	- if the element only contains text, returns the text. Otherwise returns the empty string
function element.getAttribute
	- gets an attribute value, or the empty string
sha1
	- The sha1 hashing algorithm. Output is in hex.

--
Waqas Hussain