You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@subversion.apache.org by st...@apache.org on 2013/03/06 23:15:36 UTC
svn commit: r1453590 - in /subversion/branches/fsfs-format7/subversion:
include/private/svn_string_private.h libsvn_subr/string.c
Author: stefan2
Date: Wed Mar 6 22:15:36 2013
New Revision: 1453590
URL: http://svn.apache.org/r1453590
Log:
On the fsfs-format7 branch: Introduce uint <-> string conversion
functions that operate on base36 strings as they are used within
our node, copy and txn ids.
This is the first of a long list of commits that tries to break
down the 5k lines patch I wrote to replace the internal usage of
string IDs with numerical IDs.
* subversion/include/private/svn_string_private.h
(svn__ui64tobase36,
svn__base36toui64): declare new private API functions
* subversion/libsvn_subr/string.c
(svn__ui64tobase36,
svn__base36toui64): implement them
Modified:
subversion/branches/fsfs-format7/subversion/include/private/svn_string_private.h
subversion/branches/fsfs-format7/subversion/libsvn_subr/string.c
Modified: subversion/branches/fsfs-format7/subversion/include/private/svn_string_private.h
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-format7/subversion/include/private/svn_string_private.h?rev=1453590&r1=1453589&r2=1453590&view=diff
==============================================================================
--- subversion/branches/fsfs-format7/subversion/include/private/svn_string_private.h (original)
+++ subversion/branches/fsfs-format7/subversion/include/private/svn_string_private.h Wed Mar 6 22:15:36 2013
@@ -167,6 +167,30 @@ svn__ui64toa_sep(apr_uint64_t number, ch
char *
svn__i64toa_sep(apr_int64_t number, char seperator, apr_pool_t *pool);
+
+/** Writes the @a number as base36-encoded string into @a dest. The latter
+ * must provide space for at least #SVN_INT64_BUFFER_SIZE characters.
+ * Returns the number chars written excluding the terminating NUL.
+ *
+ * @note The actual maximum buffer requirement is much shorter than
+ * #SVN_INT64_BUFFER_SIZE but introducing yet another constant is only
+ * marginally useful and may open the door to security issues when e.g.
+ * switching between base10 and base36 encoding.
+ */
+apr_size_t
+svn__ui64tobase36(char *dest, apr_uint64_t number);
+
+/** Returns the value of the base36 encoded unsigned integer starting at
+ * @a source. If @a next is not NULL, @a *next will be set to the first
+ * position after the integer.
+ *
+ * The data in @a source will be considered part of the number to parse
+ * as long as the characters are within the base36 range. If there are
+ * no such characters to begin with, 0 is returned.
+ */
+apr_uint64_t
+svn__base36toui64(const char **next, const char *source);
+
/**
* Computes the similarity score of STRA and STRB. Returns the ratio
* of the length of their longest common subsequence and the average
Modified: subversion/branches/fsfs-format7/subversion/libsvn_subr/string.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-format7/subversion/libsvn_subr/string.c?rev=1453590&r1=1453589&r2=1453590&view=diff
==============================================================================
--- subversion/branches/fsfs-format7/subversion/libsvn_subr/string.c (original)
+++ subversion/branches/fsfs-format7/subversion/libsvn_subr/string.c Wed Mar 6 22:15:36 2013
@@ -1177,6 +1177,85 @@ svn__i64toa_sep(apr_int64_t number, char
return apr_pstrdup(pool, buffer);
}
+apr_size_t
+svn__ui64tobase36(char *dest, apr_uint64_t value)
+{
+ char *dest_start = dest;
+ if (value < 10)
+ {
+ /* pretty frequent and trivial case. Make it fast. */
+ *(dest++) = (char)(value) + '0';
+ }
+ else
+ {
+ char buffer[SVN_INT64_BUFFER_SIZE];
+ char *p = buffer;
+
+ /* write result as little-endian to buffer */
+ while (value > 0)
+ {
+ char c = (char)(value % 36);
+ value /= 36;
+
+ *p = (c <= 9) ? (c + '0') : (c - 10 + 'a');
+ ++p;
+ }
+
+ /* copy as big-endian to DEST */
+ while (p > buffer)
+ *(dest++) = *(--p);
+ }
+
+ *dest = '\0';
+ return dest - dest_start;
+}
+
+apr_uint64_t
+svn__base36toui64(const char **next, const char *source)
+{
+ apr_uint64_t result = 0;
+ apr_uint64_t factor = 1;
+ int i = 0;
+ char digits[SVN_INT64_BUFFER_SIZE];
+
+ /* convert digits to numerical values and count the number of places */
+ while (TRUE)
+ {
+ char c = *source;
+ if (c < 'a')
+ {
+ /* includes detection of NUL terminator */
+ if (c < '0' || c > '9')
+ break;
+
+ c -= '0';
+ }
+ else
+ {
+ if (c < 'a' || c > 'z')
+ break;
+
+ c -= 'a' - 10;
+ }
+
+ digits[i++] = c;
+ source++;
+ }
+
+ /* fold digits into the result */
+ while (i > 0)
+ {
+ result += factor * (apr_uint64_t)digits[--i];
+ factor *= 36;
+ }
+
+ if (next)
+ *next = source;
+
+ return result;
+}
+
+
unsigned int
svn_cstring__similarity(const char *stra, const char *strb,
svn_membuf_t *buffer, apr_size_t *rlcs)
Re: svn commit: r1453590 - in /subversion/branches/fsfs-format7/subversion:
include/private/svn_string_private.h libsvn_subr/string.c
Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Thu, Mar 7, 2013 at 3:52 PM, C. Michael Pilato <cm...@collab.net>wrote:
> On 03/06/2013 05:15 PM, stefan2@apache.org wrote:
> > Author: stefan2
> > Date: Wed Mar 6 22:15:36 2013
> > New Revision: 1453590
> >
> > URL: http://svn.apache.org/r1453590
> > Log:
> > On the fsfs-format7 branch: Introduce uint <-> string conversion
> > functions that operate on base36 strings as they are used within
> > our node, copy and txn ids.
> >
> > This is the first of a long list of commits that tries to break
> > down the 5k lines patch I wrote to replace the internal usage of
> > string IDs with numerical IDs.
> >
> > * subversion/include/private/svn_string_private.h
> > (svn__ui64tobase36,
> > svn__base36toui64): declare new private API functions
> >
> > * subversion/libsvn_subr/string.c
> > (svn__ui64tobase36,
> > svn__base36toui64): implement them
>
> Maybe I missed it, but I didn't see anything by way of overflow protection
> here in the base36 -> uint64 direction. It may be an (*extremely*)
> unlikely
> scenario, but as a guy reading this code down the road, it'd be nice to see
> -- if only in a comment -- that it was something we've thought about.
>
Thanks for the review!
There was an actual buffer overflow condition that's
now fixed (r1454307). Same revision documents that
the results are "undefined" in case of an overflow.
-- Stefan^2.
--
Certified & Supported Apache Subversion Downloads:
*
http://www.wandisco.com/subversion/download
*
Re: svn commit: r1453590 - in /subversion/branches/fsfs-format7/subversion:
include/private/svn_string_private.h libsvn_subr/string.c
Posted by "C. Michael Pilato" <cm...@collab.net>.
On 03/06/2013 05:15 PM, stefan2@apache.org wrote:
> Author: stefan2
> Date: Wed Mar 6 22:15:36 2013
> New Revision: 1453590
>
> URL: http://svn.apache.org/r1453590
> Log:
> On the fsfs-format7 branch: Introduce uint <-> string conversion
> functions that operate on base36 strings as they are used within
> our node, copy and txn ids.
>
> This is the first of a long list of commits that tries to break
> down the 5k lines patch I wrote to replace the internal usage of
> string IDs with numerical IDs.
>
> * subversion/include/private/svn_string_private.h
> (svn__ui64tobase36,
> svn__base36toui64): declare new private API functions
>
> * subversion/libsvn_subr/string.c
> (svn__ui64tobase36,
> svn__base36toui64): implement them
Maybe I missed it, but I didn't see anything by way of overflow protection
here in the base36 -> uint64 direction. It may be an (*extremely*) unlikely
scenario, but as a guy reading this code down the road, it'd be nice to see
-- if only in a comment -- that it was something we've thought about.
--
C. Michael Pilato <cm...@collab.net>
CollabNet <> www.collab.net <> Enterprise Cloud Development