CodeMagic: serialize_with_cache - an approach to serializing and de-serializing arbitrary data in bash using an MRU cache

#!/bin/bash
#
# serialize_with_cache demonstrates an approach to serializing
# and de-serializing arbitrary data in bash.  This version explores
# the use of a cache to accelerate conversion of characters in the
# serialization string. The cache improves serialization performance
# on typical text by about 25%. However, performance is still quite
# slow so that string serialization using native bash mechanisms
# remains infeasible for anything but small datasets. 
#
# A simple way to run the script is by invoking:
#
#     ./serialize_with_cache.sh
#
# serialize_with_cache then runs a small self-test harness. The test
# exercises several small string serializations and de-serializations
# and then times a cycle of deflating and re-inflating the contents of
# a common system file (read only, of course) as well as measuring the
# performance speed-up due to cache effects.
# 
# Copyright (c) 2008 Technetra Corp
# 
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:
# 
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.
#
PASSED=0
TOTAL=0
I=1
MRU[0]="za61"
CACHE_SIZE=200
find_char_no_cache() {
  #sleep 1
  local hex_result=$1
  local in_char=$2
  local hex_digits1 hex_digits2=(0 1 2 3 4 5 6 7 8 9 A B C D E F)
  if [[ "$in_char" > $'\x6f' ]]; then
    hex_digits1=(7 8 9 A B C D E F)
  elif [[ "$in_char" > $'\x5f' ]]; then
    hex_digits1=(6)
  elif [[ "$in_char" > $'\x4f' ]]; then
    hex_digits1=(5)
  elif [[ "$in_char" > $'\x3f' ]]; then
    hex_digits1=(4)
  elif [[ "$in_char" > $'\x2f' ]]; then
    hex_digits1=(3)
  elif [[ "$in_char" > $'\x1f' ]]; then
    hex_digits1=(2)
  else
    hex_digits1=(0 1)
  fi
  local finished=0
  local c t targ hxi hxj
  for hxi in ${hex_digits1[@]}; do
    for hxj in ${hex_digits2[@]}; do
      c=$hxi$hxj
      #t="`eval echo z\$\'\\\x$c\'z`"
      t="`echo -e "z\x${c}z"`"
      targ=${t:1:1}
      if [[ "$in_char" == "$targ" ]]; then
        #echo "matched character index $c"
        finished=1
        break
      fi
    done
    [[ $finished -eq 1 ]] && break
  done
  eval $hex_result=$c
} 
find_char_with_cache() {
  #sleep 1
  local hex_result=$1
  local in_char=$2
  local j=$(((I+(CACHE_SIZE-1))%CACHE_SIZE))
  while [[ j -ne I%CACHE_SIZE ]]; do
    m="${MRU[j]}"
    if [[ "$m" ]]; then
      j=$(((j+(CACHE_SIZE-1))%CACHE_SIZE))
      if [[ "${m:1:1}" == "$in_char" ]]; then
        eval $hex_result=${m:2:2}
        #echo "got cache hit \"$in_char\""
        I=$((I%CACHE_SIZE))
        MRU[I++]="`echo -e "z$in_char${m:2:2}"`"
        return
      fi 
    else
      #echo "missed cache for \"$in_char\""
      break
    fi
    #sleep 1
  done 
  local hex_digits1 hex_digits2=(0 1 2 3 4 5 6 7 8 9 A B C D E F)
  if [[ "$in_char" > $'\x6f' ]]; then
    hex_digits1=(7 8 9 A B C D E F)
  elif [[ "$in_char" > $'\x5f' ]]; then
    hex_digits1=(6)
  elif [[ "$in_char" > $'\x4f' ]]; then
    hex_digits1=(5)
  elif [[ "$in_char" > $'\x3f' ]]; then
    hex_digits1=(4)
  elif [[ "$in_char" > $'\x2f' ]]; then
    hex_digits1=(3)
  elif [[ "$in_char" > $'\x1f' ]]; then
    hex_digits1=(2)
  else
    hex_digits1=(0 1)
  fi
  local finished=0
  local c t targ hxi hxj
  for hxi in ${hex_digits1[@]}; do
    for hxj in ${hex_digits2[@]}; do
      c=$hxi$hxj
      #t="`eval echo z\$\'\\\x$c\'z`"
      t="`echo -e "z\x${c}z"`"
      targ=${t:1:1}
      if [[ "$in_char" == "$targ" ]]; then
        #echo "matched character index $c"
        finished=1
        I=$((I%CACHE_SIZE))
        MRU[I++]="`echo -e "z$targ$c"`"
        break
      fi
    done
    [[ $finished -eq 1 ]] && break
  done
  eval $hex_result=$c
}
deflate() {
  local result=$1
  local s="$2"
  local which_find_char=$3
  local i=0 deflated out_hex
  local c="${s:i++:1}"
  while [[ "$c" ]]; do
    $which_find_char out_hex "$c"
    deflated=$deflated$out_hex
    c="${s:i++:1}"
  done 
  eval $result=$deflated
}
inflate() {
  local result=$1
  local hex_string=$2 
  local i=0 inflated t targ
  local h=${hex_string:i:2}
  i=$((i+2))
  while [[ "$h" ]]; do
    #t="`eval echo z\$\'\\\x$h\'z`"
    t="`echo -e "z\x${h}z"`"
    targ=${t:1:1}
    [[ "$targ" == '"' ]] && targ='\"'
    inflated="$inflated$targ"
    h=${hex_string:i:2}
    i=$((i+2))
  done
  eval "$result=\"$inflated\""
}
test_serialize () {
  local in_orig="$1"
  local which_find_char=${2:-find_char_with_cache}
  local stat hex copy
  deflate hex "$in_orig" $which_find_char
  inflate copy $hex
  if [[ "$in_orig" == "$copy" ]]; then
    stat=passed
    ((PASSED++))
  else
    stat=failed
  fi
  ((TOTAL++))
  echo "$stat test $TOTAL (cache=$which_find_char), hex=$hex, original=\"$in_orig\""
}
time_file () {
  echo "timing serialization for file $1..."
  test_serialize "$(cat $1)" $2
}
###
### MAIN
###
test_serialize "a\"c"
test_serialize "a\'c"
test_serialize "$(echo -e " a\n\tb")"
test_serialize "'%' in a prerequisite of a pattern rule stands for the same stem that was matched by the"
time_file /etc/passwd
echo "checking performance improvement due to cache..."
# built-in bash reserved word, time, requires execution in a subshell to capture its stderr
# output
export TIMEFORMAT=%3R
t1=`(time test_serialize "$(head -n 25 /etc/passwd)" >/dev/null) 2>&1`
echo "continuing..."
t2=`(time test_serialize "$(head -n 25 /etc/passwd)" find_char_no_cache >/dev/null) 2>&1`
# use integer arithmetic and add leading 1 to guard against misinterpretation
# as octal because of leading zeros
l1=${#t1}
l2=${#t2}
max=$((l1>l2?l1:l2))
pad=100000
pad=${pad:0:max}
z1=${pad:0:max-l1+1}${t1/./}
z2=${pad:0:max-l2+1}${t2/./}
echo "TEST SUMMARY: passed $PASSED of $TOTAL tests" \
     "(cache speed-up approx: $((((z2-z1)*100)/(z2-pad)))%)"
# end serialize_with_cache