\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#418: Add [binary] Subcommands for In-Place Modification}
\date{August 27, 2012}
\author{Jeff Rogers}
\urlstyle{sf}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}
\def\tipversion$#1${\texttt{\$#1\$}}
\def\tiplangle#1{\ensuremath{<}}
\def\tiprangle#1{\ensuremath{>}}
\def\tipbar#1{\ensuremath{|}}
\def\tipmail#1#2{\(\langle\){\small\expandafter\url{#1@#2}}\(\rangle\)}
\ifx\pdfoutput\undefined
\newcommand{\tipimage}[2]{\typeout{Make sure you download #1.eps}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.eps}}{\includegraphics[width=0.8\textwidth]{#1.eps}}}
\newcommand{\tipxref}[1]{}
\newcommand{\tipxrefend}{}
\else
\newcommand{\tipimage}[2]{\typeout{Make sure you create #1.pdf}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.pdf}}{\includegraphics[width=0.8\textwidth]{#1.pdf}}}
\pdfcatalog{/PageMode /UseOutlines}
\newcommand{\tipxref}[1]{\pdfannotlink attr {/C [0.5 0.5 1.0] /Border [0 0 1]} goto name {#1}}
\newcommand{\tipxrefend}{\pdfendlink}
\fi
\newenvironment{tipabstract}{\begin{abstract}}{\end{abstract}}
\begin{document}\maketitle
\begin{center}\begin{tabularx}{\linewidth}{|r@{: }X|}\hline
\textbf{TIP \#418}&\textbf{Add [binary] Subcommands for In-Place Modification}\\\hline
Author&

Jeff Rogers \tipmail{dvrsn}{diphi.com}
\\
Created&Monday, \(\text{27}^{\text{th}}\) August 2012\\
Type&Project\\
Tcl Version&\(8.7\)\\
State&Draft\\
Vote&Pending\\
Version&\tipversion$Revision: 1.3 $\\
Keywords&Tcl, binary data\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP proposes adding new subcommands to the \textbf{binary} to better enable parsing and manipulation of binary values.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

The \textbf{binary} command efficiently deals with creating new objects or completely parsing existing ones, but it does not handle modifying existing binary objects or parsing them a little bit at a time. A few new subcommands would greatly improve the performance of these operations on large objects.

\subsection{Variable vs. Value}

While it will be possible to implement these modification operations as standard copy-on-write operations taking a value instead of a variable name, I believe this would result in copying unless the well-known but still clumsy technique of unsetting the variable after reading it (i.e., [K \$x [set x \{\}]]) is used. This TIP is intended to fix this by providing a more convenient and simpler-to-use mechanism which also admits more efficient implementation.

\section{Specification}

Two new core subcommands are proposed: \textbf{binary edit} modifies an existing byte array ``in place''; and \textbf{binary scanshift} parse data from a byte array and removes the data that was parsed. The intent is that additional commands can be built on top of these in library code.

The existing \textbf{binary} commands already make use of an internal cursor; that notion is extensively used by these new commands.

\subsection{Binary Edit}

\begin{quote}
\textbf{binary edit} \textit{varName formatStr} ?\textit{value value ...}?
\end{quote}

This is similar to \textbf{binary format} except that the initial value of the new byte array is an existing object stored in a variable rather than an array of nulls.

Format specifiers in \textit{formatStr} are as in \textbf{binary format} except:
\begin{itemize}
\item{}
fixed-width format specifiers (e.g., \textbf{c}, \textbf{s}, \textbf{i}) that do not have enough values in their corresponding argument (importantly, if they have 0 values) move the cursor by the appropriate width.
\item{}
New \textbf{z} and \textbf{Z} format specifiers are introduced that move the cursor forward or backward in the binary string without writing anything and consume no arguments. \textbf{Z} is a synonym for ``X'', provided for symmetry. A count of ``\textbf{*}'' for the ``\textbf{z}'' format moves the cursor to the end of the existing object.
\end{itemize}

After the format string and all arguments have been processed, the length of the string is adjusted to end at the current cursor position.

Thus, a format string that starts with ``z*'' will append to the existing value, and one that ends with ``z*'' will keep the length the same.

\subsection{Binary Scanshift}

\begin{quote}
\textbf{binary scanshift} \textit{varName formatStr} ?\textit{var var var ...}?
\end{quote}

This works like \textbf{binary scan} except that after the format string has been processed and all variables assigned to, all data in the string before the ending location of the cursor is discarded.

Thus,
\begingroup\small\begin{verbatim}
binary scanshift bvar c byte1
binary scanshift bvar c byte2
binary scanshift bvar c byte3
\end{verbatim}
\endgroup

Will put the first 3 bytes of the binary \textit{\$bvar} into \textit{byte1}, \textit{byte2}, and \textit{byte3}, with \textit{bvar} being subsequently three bytes shorter (the missing bytes being the first three).

This is useful to avoid keeping a separate external cursor variable that must be incremented and re-used on each iteration.

\subsection{Additional Library Commands}

Suggested additional library commands are \textbf{poke} and \textbf{append}. The arguments to \textbf{binary poke} will be:

\begin{quote}
\textbf{binary poke} \textit{varName index formatStr} ?\textit{var ...}?
\end{quote}

This moves the cursor to a specified index, then overwrite with the specified format string. Implemented as
\begingroup\small\begin{verbatim}
      binary edit varName "@${index} $formatStr z*" var ...
\end{verbatim}
\endgroup

The arguments to \textbf{binary append} will be:

\begin{quote}
\textbf{binary append} \textit{varName formatStr} "?\textit{var ...}?
\end{quote}

This appends the given formatted data to an existing var. Implemented as
\begingroup\small\begin{verbatim}
      binary edit varName "z* $formatStr" ?var ...?"
\end{verbatim}
\endgroup

\section{Implementation Notes}

Efficient implementation of the ``\textbf{scanshift}'' subcommand requires a new ``offset'' field in the ByteArray structure and any operations that read the object (particularly duplicating it and updating the string representation) need to be aware of this field. All external interfaces should be unaffected, as the ByteArray structure type is private to tclBinary.c, And since it's internal, EIAS is not violated.

When extending an existing byte array with the ``\textbf{edit}'' subcommand, care should be taken with memory allocation to avoid repeated \textit{realloc()} and \textit{memcpy()} operations. It is a reasonable assumption that a given byte array will be extended repeatedly or not at all beyond the initial creation. So a memory allocation strategy is to allocate the exact length initially (i.e., when adjusting the size from 0 to non-zero) and allocating double the requested length subsequently a typical allocation-doubling strategy should work well. A double allocation should not be needed for an initial extension (i.e., extending from 0 to some length) as that is typically the case when a binary object is first created, and most binary objects will probably not be extended; but once extended it is reasonable to prepare for more of the same.

After numerous ``\textbf{scanshift}'' operations there will be wasted space at the beginning of the memory allocated for the data. One strategy for keeping this under control would be to move the live data to the beginning of the allocated space when the offset is larger than the live data, so that the memory could be copied without worrying about overlap; and this would also leave the allocation size at roughly double the live data size.

\section{Reference Implementation}

Forthcoming.

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\end{document}
