/*
pathencode.c - efficient path name encoding
Copyright 2012 Facebook
This software may be used and distributed according to the terms of
the GNU General Public License, incorporated herein by reference.
*/
/*
* An implementation of the name encoding scheme used by the fncache
* store. The common case is of a path < 120 bytes long, which is
* handled either in a single pass with no allocations or two passes
* with a single allocation. For longer paths, multiple passes are
* required.
*/
#include <Python.h>
#include <assert.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include "util.h"
/* state machine for the fast path */
enum path_state {
START, /* first byte of a path component */
A, /* "AUX" */
AU,
THIRD, /* third of a 3-byte sequence, e.g. "AUX", "NUL" */
C, /* "CON" or "COMn" */
CO,
COMLPT, /* "COM" or "LPT" */
COMLPTn,
L,
LP,
N,
NU,
P, /* "PRN" */
PR,
LDOT, /* leading '.' */
DOT, /* '.' in a non-leading position */
H, /* ".h" */
HGDI, /* ".hg", ".d", or ".i" */
SPACE,
DEFAULT, /* byte of a path component after the first */
};
/* state machine for dir-encoding */
enum dir_state {
DDOT,
DH,
DHGDI,
DDEFAULT,
};
static inline int inset(const uint32_t bitset[], char c)
{
return bitset[((uint8_t)c) >> 5] & (1 << (((uint8_t)c) & 31));
}
static inline void charcopy(char *dest, Py_ssize_t *destlen, size_t destsize,
char c)
{
if (dest) {
assert(*destlen < destsize);
dest[*destlen] = c;
}
(*destlen)++;
}
static inline void memcopy(char *dest, Py_ssize_t *destlen, size_t destsize,
const void *src, Py_ssize_t len)
{
if (dest) {
assert(*destlen + len < destsize);
memcpy((void *)&dest[*destlen], src, len);
}
*destlen += len;
}
static inline void hexencode(char *dest, Py_ssize_t *destlen, size_t destsize,
uint8_t c)
{
static const char hexdigit[] = "0123456789abcdef";
charcopy(dest, destlen, destsize, hexdigit[c >> 4]);
charcopy(dest, destlen, destsize, hexdigit[c & 15]);
}
/* 3-byte escape: tilde followed by two hex digits */
static inline void escape3(char *dest, Py_ssize_t *destlen, size_t destsize,
char c)
{
charcopy(dest, destlen, destsize, '~');
hexencode(dest, destlen, destsize, c);
}
static Py_ssize_t _encodedir(char *dest, size_t destsize,
const char *src, Py_ssize_t len)
{
enum dir_state state = DDEFAULT;
Py_ssize_t i = 0, destlen = 0;
while (i < len) {
switch (state) {
case DDOT:
switch (src[i]) {
case 'd':
case 'i':
state = DHGDI;
charcopy(dest, &destlen, destsize, src[i++]);
break;
case 'h':
state = DH;
charcopy(dest, &destlen, destsize, src[i++]);
break;
default:
state = DDEFAULT;
break;
}
break;
case DH:
if (src[i] == 'g') {
state = DHGDI;
charcopy(dest, &destlen, destsize, src[i++]);
}
else state = DDEFAULT;
break;
case DHGDI:
if (src[i] == '/') {
memcopy(dest, &destlen, destsize, ".hg", 3);
charcopy(dest, &destlen, destsize, src[i++]);
}
state = DDEFAULT;
break;
case DDEFAULT:
if (src[i] == '.')
state = DDOT;
charcopy(dest, &destlen, destsize, src[i++]);
break;
}
}
return destlen;
}
PyObject *encodedir(PyObject *self, PyObject *args)
{
Py_ssize_t len, newlen;
PyObject *pathobj, *newobj;
char *path;
if (!PyArg_ParseTuple(args, "O:encodedir", &pathobj))
return NULL;
if (PyString_AsStringAndSize(pathobj, &path, &len) == -1) {
PyErr_SetString(PyExc_TypeError, "expected a string");
return NULL;
}
newlen = len ? _encodedir(NULL, 0, path, len + 1) : 1;
if (newlen == len + 1) {
Py_INCREF(pathobj);
return pathobj;
}
newobj = PyString_FromStringAndSize(NULL, newlen);
if (newobj) {
PyString_GET_SIZE(newobj)--;
_encodedir(PyString_AS_STRING(newobj), newlen, path,
len + 1);
}
return newobj;
}
static Py_ssize_t _encode(const uint32_t twobytes[8], const uint32_t onebyte[8],
char *dest, Py_ssize_t destlen, size_t destsize,
const char *src, Py_ssize_t len,
int encodedir)
{
enum path_state state = START;
Py_ssize_t i = 0;
/*
* Python strings end with a zero byte, which we use as a
* terminal token as they are not valid inside path names.
*/
while (i < len) {
switch (state) {
case START:
switch (src[i]) {
case '/':
charcopy(dest, &destlen, destsize, src[i++]);
break;
case '.':
state = LDOT;
escape3(dest, &destlen, destsize, src[i++]);
break;
case ' ':
state = DEFAULT;
escape3(dest, &destlen, destsize, src[i++]);
break;
case 'a':
state = A;
charcopy(dest, &destlen, destsize, src[i++]);
break;
case 'c':
state = C;
charcopy(dest, &destlen, destsize, src[i++]);
break;
case 'l':
state = L;
charcopy(dest, &destlen, destsize, src[i++]);
break;
case 'n':
state = N;
charcopy(dest, &destlen, destsize, src[i++]);
break;
case 'p':
state = P;
charcopy(dest, &destlen, destsize, src[i++]);
break;
default:
state = DEFAULT;
break;
}
break;
case A:
if (src[i] == 'u') {
state = AU;
charcopy(dest, &destlen, destsize, src[i++]);
}
else state = DEFAULT;
break;
case AU:
if (src[i] == 'x') {
state = THIRD;
i++;
}
else state = DEFAULT;
break;
case THIRD:
state = DEFAULT;
switch (src[i]) {
case '.':
case '/':
case '\0':
escape3(dest, &destlen, destsize, src[i - 1]);
break;
default:
i--;
break;
}
break;
case C:
if (src[i] == 'o') {
state = CO;
charcopy(dest, &destlen, destsize, src[i++]);
}
else state = DEFAULT;
break;
case CO:
if (src[i] == 'm') {
state = COMLPT;
i++;
}
else if (src[i] == 'n') {
state = THIRD;
i++;
}
else state = DEFAULT;
break;
case COMLPT:
switch (src[i]) {
case '1': case '2': case '3': case '4': case '5':
case '6': case '7': case '8': case '9':
state = COMLPTn;
i++;
break;
default:
state = DEFAULT;
charcopy(dest, &destlen, destsize, src[i - 1]);
break;
}
break;
case COMLPTn:
state = DEFAULT;
switch (src[i]) {
case '.':
case '/':
case '\0':
escape3(dest, &destlen, destsize, src[i - 2]);
charcopy(dest, &destlen, destsize, src[i - 1]);
break;
default:
memcopy(dest, &destlen, destsize,
&src[i - 2], 2);
break;
}
break;
case L:
if (src[i] == 'p') {
state = LP;
charcopy(dest, &destlen, destsize, src[i++]);
}
else state = DEFAULT;
break;
case LP:
if (src[i] == 't') {
state = COMLPT;
i++;
}
else state = DEFAULT;
break;
case N:
if (src[i] == 'u') {
state = NU;
charcopy(dest, &destlen, destsize, src[i++]);
}
else state = DEFAULT;
break;
case NU:
if (src[i] == 'l') {
state = THIRD;
i++;
}
else state = DEFAULT;
break;
case P:
if (src[i] == 'r') {
state = PR;
charcopy(dest, &destlen, destsize, src[i++]);
}
else state = DEFAULT;
break;
case PR:
if (src[i] == 'n') {
state = THIRD;
i++;
}
else state = DEFAULT;
break;
case LDOT:
switch (src[i]) {
case 'd':
case 'i':
state = HGDI;
charcopy(dest, &destlen, destsize, src[i++]);
break;
case 'h':
state = H;
charcopy(dest, &destlen, destsize, src[i++]);
break;
default:
state = DEFAULT;
break;
}
break;
case DOT:
switch (src[i]) {
case '/':
case '\0':
state = START;
memcopy(dest, &destlen, destsize, "~2e", 3);
charcopy(dest, &destlen, destsize, src[i++]);
break;
case 'd':
case 'i':
state = HGDI;
charcopy(dest, &destlen, destsize, '.');
charcopy(dest, &destlen, destsize, src[i++]);
break;
case 'h':
state = H;
memcopy(dest, &destlen, destsize, ".h", 2);
i++;
break;
default:
state = DEFAULT;
charcopy(dest, &destlen, destsize, '.');
break;
}
break;
case H:
if (src[i] == 'g') {
state = HGDI;
charcopy(dest, &destlen, destsize, src[i++]);
}
else state = DEFAULT;
break;
case HGDI:
if (src[i] == '/') {
state = START;
if (encodedir)
memcopy(dest, &destlen, destsize, ".hg",
3);
charcopy(dest, &destlen, destsize, src[i++]);
}
else state = DEFAULT;
break;
case SPACE:
switch (src[i]) {
case '/':
case '\0':
state = START;
memcopy(dest, &destlen, destsize, "~20", 3);
charcopy(dest, &destlen, destsize, src[i++]);
break;
default:
state = DEFAULT;
charcopy(dest, &destlen, destsize, ' ');
break;
}
break;
case DEFAULT:
while (inset(onebyte, src[i])) {
charcopy(dest, &destlen, destsize, src[i++]);
if (i == len)
goto done;
}
switch (src[i]) {
case '.':
state = DOT;
i++;
break;
case ' ':
state = SPACE;
i++;
break;
case '/':
state = START;
charcopy(dest, &destlen, destsize, '/');
i++;
break;
default:
if (inset(onebyte, src[i])) {
do {
charcopy(dest, &destlen,
destsize, src[i++]);
} while (i < len &&
inset(onebyte, src[i]));
}
else if (inset(twobytes, src[i])) {
char c = src[i++];
charcopy(dest, &destlen, destsize, '_');
charcopy(dest, &destlen, destsize,
c == '_' ? '_' : c + 32);
}
else
escape3(dest, &destlen, destsize,
src[i++]);
break;
}
break;
}
}
done:
return destlen;
}
static Py_ssize_t basicencode(char *dest, size_t destsize,
const char *src, Py_ssize_t len)
{
static const uint32_t twobytes[8] = { 0, 0, 0x87fffffe };
static const uint32_t onebyte[8] = {
1, 0x2bff3bfa, 0x68000001, 0x2fffffff,
};
Py_ssize_t destlen = 0;
return _encode(twobytes, onebyte, dest, destlen, destsize,
src, len, 1);
}
static const Py_ssize_t maxstorepathlen = 120;
/*
* We currently implement only basic encoding.
*
* If a name is too long to encode due to Windows path name limits,
* this function returns None.
*/
PyObject *pathencode(PyObject *self, PyObject *args)
{
Py_ssize_t len, newlen;
PyObject *pathobj, *newobj;
char *path;
if (!PyArg_ParseTuple(args, "O:pathencode", &pathobj))
return NULL;
if (PyString_AsStringAndSize(pathobj, &path, &len) == -1) {
PyErr_SetString(PyExc_TypeError, "expected a string");
return NULL;
}
if (len > maxstorepathlen) {
newobj = Py_None;
Py_INCREF(newobj);
return newobj;
}
newlen = len ? basicencode(NULL, 0, path, len + 1) : 1;
if (newlen <= maxstorepathlen + 1) {
if (newlen == len + 1) {
Py_INCREF(pathobj);
return pathobj;
}
newobj = PyString_FromStringAndSize(NULL, newlen);
if (newobj) {
PyString_GET_SIZE(newobj)--;
basicencode(PyString_AS_STRING(newobj), newlen, path,
len + 1);
}
} else {
newobj = Py_None;
Py_INCREF(newobj);
}
return newobj;
}