Алексей Пахунов

Just for fun, раз уж комментов пока нет:

size_t recv(char *buf, size_t size)
{
short int length;

((char*)&length)[0] = get_byte();
((char*)&length)[1] = get_byte();

if(size < length)
{
for(int i = 0; i < length – 2; i++)
get_byte();
return 0;
}
else
{
((short int*)buf)[0] = length;
for(int i = 2; i < length; i++)
buf[i] = get_byte();
return length;
}
}

Так как не совсем понятно, что считать ошибкой при указанных условиях, я считаю, что ошибкой является недостаточный размер буфера. Пакет в этом случае я все равно вычитываю весь, потому что функций для запихивания байтов обратно нет.

Написал в текстовом редакторе, не проверял и даже не компилировал ) Ну что, какие ошибки?

Возможно я что-то не так понимаю, но это же довольно простая задача, студентам на зачёте можно давать в качестве вопроса на три?

get_byte должна возвращать int а не char, иначе как тогда отлавливать конец потока?

в чём сложность?
имхо, только в определении LE/BE единственного поля.

size_t recv(char* buf, size_t size)
{
uint16_t len, i;
uint8_t hdr1, hdr2;

// size как минимум 2, под заголовок
if (!buf || size < 2)
return 0;
// получаем заголовок
hdr1 = get_byte();
hdr2 = get_byte();
// превращаем 2 разрозненных байта в одно число
#ifdef _LITTLE_ENDIAN_
len = hdr1 || (hdr2 << 8);
#else
len = hdr2 || (hdr1 << 8);
#endif
if (size < len)
return 0;
// сохраняем в буффер
*buf = hdr1;
buf++;
*buf = hdr2;
buf++;
// забираем пакет
for (i = 2; i < len; i++)
{
*buf = get_byte();
buf++;
}
return len;
}

Функции recv придется хранить контекст где-то.
Потому что размер буфера может быть меньше, чем размер пакета, но чтобы узнать это – мы должны вычитать два байта из входного потока, а функции “вернутся назад на два байта, чтобы поток остался на границе пакета” я что-то не вижу. Т.е. при ошибке мы должны где-то сохранить размер пакета и флаг, что мы находимся во входном потоке не на границе пакета, а после его заголовка.

size_t recv(char* buf, size_t size) {
char bSize, bData;
size_t uBufPos;
if(size<1) { return 0; }
uBufPos=0;
bSize = get_byte();
buf[uBufPos] = bSize; uBufPos++;
while (uBufPos=size) { return 0; }
bData = get_byte();
buf[uBufPos] = bData;
uBufPos++;
}
return bSize;
}

> size_t recv(char* buf, size_t size);

Тогда, наверное, char** buf. Ведь нам нужно передать в функцию указатель не на один char, а на блок char*. Хотя разницы никакой, адрес есть адрес.

Опущено ключевое условие – не сказано о таймауте. Без этого сложно будет корректно написать функцию.

Кривокомментарий сожрал часть кода, вот правильно.

size_t recv(char* buf, size_t size) {
char bSize, bData;
size_t uBufPos;
if(size<1) { return 0; }
uBufPos=0;
bSize = get_byte();
buf[uBufPos] = bSize; uBufPos++;
while (uBufPos<=size) {
if(size<=uBufPos) { return 0; }
bData = get_byte();
buf[uBufPos] = bData;
uBufPos++;
}
return bSize;
}

Тьфу, с ошибкой восстановил, вот правильно.
size_t recv(char* buf, size_t size) {
char bSize, bData;
size_t uBufPos;
if(size<1) { return 0; }
uBufPos=0;
bSize = get_byte();
buf[uBufPos] = bSize; uBufPos++;
while (uBufPos<=bSize) {
if(size<=uBufPos) { return 0; }
bData = get_byte();
buf[uBufPos] = bData;
uBufPos++;
}
return bSize;
}

А если буфер слишком мал как об этом сказать пользователю?

size_t recv(char *buf, size_t size)
{
size_t bufIdx = 2;
size_t length;

if (size < 2)
return 0;

buf[0] = get_byte();
buf[1] = get_byte();
length = ntohs(*((unsigned short*)buf));

while (bufIdx < length && bufIdx < size) {
buf[bufIdx] = get_byte();
bufIdx++;
}

return bufIdx;
}

Виноват, невнимательно прочитал условие.

size_t recv(char *buf, size_t size)
{
size_t bufIdx = 2;
char lenBuf[2];
size_t length;

// чтобы по возможности не портить состояние потока
if (!buf || size < 2)
return 0;

lenBuf[0] = get_byte();
lenBuf[1] = get_byte();
length = ntohs(*((unsigned short*)lenBuf));

// ничего не поделаешь, состояние потока испорчено
if (size < length)
return 0;

while (bufIdx < length) {
buf[bufIdx] = get_byte();
bufIdx++;
}

return bufIdx;
}

я написал так, но камменты натолкнули на интересную мысль, если буфер меньше чем пакет, наверное нужно съесть пакет, хотя по хорошему пожалуй стоило бы откатить 2 байта длины пакета в поток и вернуть ошибку

#include

char buf[] = {2, 0, 1, 2};
int bufPos = 0;
char get_byte()
{
return buf[bufPos++];
}

size_t recv(char *buf, size_t size)
{
if(!buf || size < 2)
return 0;

size_t lowLen = get_byte();
size_t highLen = get_byte();

size_t length = highLen << 8 | lowLen;
if(length + 2 <= size) {
(*buf++) = lowLen;
(*buf++) = highLen;
int i;
for(i = 0; i < length; i++)
(*buf++) = get_byte();

return length + 2;
}

return 0;
}

int main()
{
char * buf = (char *)malloc(4);
size_t len = recv(buf, 4);
printf("Size: %d\nData: %d, %d, %d, %d\n", (int)len, buf[0], buf[1], buf[2], buf[3]);
free(buf);
}

Блин, да что же я такое пишу!

size_t recv(char *buf, size_t size)
{
size_t bufIdx = 2;
size_t length;

// чтобы по возможности не портить состояние потока, если даже длину
// некуда прочесть
if (!buf || size < 2)
return 0;

buf[0] = get_byte();
buf[1] = get_byte();
length = ntohs(*((unsigned short*)buf));

// писать пакет некуда – ничего не поделаешь, состояние потока испорчено;
// по-хорошему, надо прочитанные два байта засунуть обратно в поток
if (size < length)
return 0;

while (bufIdx < length) {
buf[bufIdx] = get_byte();
bufIdx++;
}

return length;
}

Ой, а зачем так сложно-то делают все? Можно же просто в лоб сделать, и при этом не терять данные в случае маленького буфера.

size_t recv(char *buf, size_t size)
{
if(size < 2) return 0;
static WORD len = 0;
if(!len)
{
buf[0] = getbyte();
buf[1] = getbyte();
len = buf[0] + buf[1] << 8;
}
if(size < len)
{
return 0;
}
for(WORD i = 2; i < len; ++i)
{
buf[i] = getbyte();
}
return len;
}

size_t recv(char* buf, size_t size)
{
unsigned short packSize = (get_byte(0) < size)
{
return 0;
}
buf[0] = (char)(packSize >> 8);
buf[1] = (char)packSize;
unsigned short index = 2;
while (packSize > index)
{
buf[index] = get_byte(3);
index++;
}
return packSize;
}

обрезало “|”

тогда так

size_t recv(char* buf, size_t size)
{
unsigned short packSize = (get_byte() < size)
{
return 0;
}
buf[0] = (char)(packSize >> 8);
buf[1] = (char)packSize;
unsigned short index = 2;
while (packSize > index)
{
buf[index] = get_byte();
index++;
}
return packSize;
}

@Misha
странно ведет себя коментарии с “|”

size_t recv(char* buf, size_t size)
{
unsigned short packSize = (get_byte() < size)
{
return 0;
}
buf[0] = (char)(packSize >> 8);
buf[1] = (char)packSize;
unsigned short index = 2;
while (packSize > index)
{
buf[index] = get_byte();
index++;
}
return packSize;
}

@Misha
Все равно обрезал, тогда так

size_t recv(char* buf, size_t size)
{
unsigned short packSize = (get_byte() < size)
{
return 0;
}
buf[0] = (char)(packSize >> 8);
buf[1] = (char)packSize;
unsigned short index = 2;
while (packSize > index)
{
buf[index] = get_byte();
index++;
}
return packSize;
}

собственно нужно знать нэйтивный порядок байт на целевой платформе

Александр Бакулин :
length = ntohs(*((unsigned short*)buf));

и почему все выдрюкиваются с указателями, вместо того чтобы просто умножить и сложить?

@Bogdan

Почти уверен, что у вас решение имеет изъяв в виде разницы low endian и high-endian архитектур

для gcc, msvs не скушает __attribute__ и char data[0]

struct packet_
{
uint16_t size;
char data[0];
} __attribute__ ((packed));

typedef struct packet_ packet_t;

size_t recv(char* buffer, size_t size)
{
if (size size = ( (uint8_t)get_byte() <size = ntohs( packet->size ); // если надо

if (size size)
return 0;

for(size_t i=0, data_size = packet->size-2 ; i data[i] = get_byte();
}

return packet->size;
}

для gcc, msvs не скушает __attribute__ и char data[0]
написано на си

struct packet_
{
uint16_t size;
char data[0];
} __attribute__ ((packed));

typedef struct packet_ packet_t;

size_t recv(char* buffer, size_t size)
{
if (size size = ( (uint8_t)get_byte() <size = ntohs( packet->size ); // если надо

if (size size)
return 0;

for(size_t i=0, data_size = packet->size-2 ; i data[i] = get_byte();
}

return packet->size;
}

@dnk
парсер покусал код, http://pastebin.com/nBVqYEra

@Tyler функция не реентерабельна

@Nikolay T. размер содержат первые ДВА байта

@Александр Бакулин портите исходный буфер, нужно только при возможности писать в него

Я уж думал удивиться, что таковых (решающих) мало находится,
а здесь такой фейспалм, что я признал себя наивным.
LE/BE – это то, о чём не подумал я, если что.

А предварительных тестовых заданий у вас не проводится?
Отчего все уже на доске это пишут, время отнимают?

Ну вот, Алексей, вон, сколько умных людей сходу решили Вашу задачку! Глядишь, так и подберете себе сотрудника.

Это кандидаты, которые

Senior SDE с опытом разработки драйверов и другого низкоуровневого кода, а так же с хорошим пониманием сетевых технологий (протоколы, драйвера, и т.п.)

на собеседовании? Алексей, опровергните, верните мне веру в человеков!
Т.е. я, не имея такового опыта, нахожусь в одном шаге от того,
чтобы быть лучше 80% из “опытных”?

Только у Богдана пакет дочитывается до конца в случае, если буфер меньше длинны пакета?

@Bogdan
Вы приняты

1. Размер пакета big endian или little?
2. Что делать, если не хватает размера буфера для приема пакета?

char get_byte();
size_t recv(char *buff, size_t size){
if(!buff || size < 2){
return 0; // invalid buffer
}
uint8_t first = get_byte();
uint8_t second = get_byte();
#if _LITTLE_ENDIAN_
uint16_t header = first;
header <<= 8;
header |= second;
#else
uint16_t header = second;
header < size){
return 0; // invalid buffer
}
if(header < 2){
return 0; // invalid header
}
char* curr = buff;
*curr = first; curr++;
*curr = second; curr++;
for(size_t i = 0; i < header – 2; ++i, curr++){
*curr = get_byte();
}
return header;
}

char get_byte();
size_t recv(char *buff, size_t size){
  if(!buff || size < 2){
    return 0; // invalid buffer
  }
  uint8_t first = get_byte();
  uint8_t second = get_byte();
#if _LITTLE_ENDIAN_
  uint16_t header = first;
  header <<= 8;
  header |= second;
#else
  uint16_t header = second;
  header <<= 8;
  header |= first;
#endif
  if(header > size){
    return 0; // invalid buffer
  }
  if(header < 2){
    return 0; // invalid header
  }
  char* curr = buff;
  *curr = first; curr++;
  *curr = second; curr++;
  for(size_t i = 0; i < header - 2; ++i, curr++){
    *curr = get_byte();
  }
  return header;
}

* This source code was highlighted with Source Code Highlighter.

Фиг пойми как тут пофиксить чтобы видно было нормально.

Тупой вопрос – какой endianness?

@Tyler
Поскольку в описании протокола не указано, какой там должен быть endianness, а задача тестовая, значит, эту проблему можно вообще игнорировать.

Те кто занимаются разработкой встраиваемых систем, такую задачу решают через день, точнее она уже давно решена.

Как правильно заметили:

1) здесь не указан порядок байт длины
2) принимаемый пакет кладём во внутренний static unsigned char буфер на 65535 элементов (потому что 2 байта длина)
3) что делать если длина равна 0 или 1? это ошибка пакета
4) что делать если пользователь нам дал буфер недостаточной длины.

Вообще алгоритмы которые закладываются на то, что все хорошо — неинтересные ибо тривиальные. Интереснее работать с алгоритмами, которые должны правильно обработать все ошибки.

внимательно посмотрел все примеры кода выше в комментах. никто не догадался проверить, что длина пакета больше или равна 2м. наколка была именно в этом?

Алексей, если успешное решение этой задачки является необходимым требованием, то у вас плохо работает предварительный отбор претендентов…

А вообще, я не вижу смысла издеваться над людьми, заставлять их писать длинный код на доске – вы там что, всё время на доске код пишете? Уж лучше дать компьютер и посмотреть, как они этот код будут писать в их любимом IDE или на худой конец в чём-нибудь блокнотоподобном – по их действиям сразу будет видно, что они знают, а с чем будут разбираться на ходу.

Ну а по задачке, первым делом я бы спросил, как у вас называется функция (или макро) конвертации двух char в int, или в этой абстрактной задачке в вакууме такую функцию ещё никто не догадался сделать? Ну а остальное напишет любой кто хоть какое-то время занимался задачками с TopCoder, SPOJ и прочими – там как раз нужно написать небольшой код, чётко соответствующий поставленному условию, а если соревноваться то ещё и чем быстрее, тем лучше. Если вам такие люди нужны – так и напишите в вакансии.

Кстати, как у вас проходит это “написание программы на доске”? Нужно писать непрерывным потоком или можно исправлять? Можно написать, потом проверить, а потом сказать – вот оно, смотрите?

Не указан endian заголовка

size_t recv(char* buf, size_t size)
{
unsigned __int16 static len = 0;

if (len)
len = get_byte() | get_byte() < size)
return 0;
*((unsigned __int16*)buf) = len;

len -=2;
buf += 2;

while (len–)
*buf++ = get_byte();

return *((unsigned __int16*)buf);
}

size_t recv(char* buf, size_t size)
{
// minimum buf size is 2 bytes for packet length
if ( size < 2 )
{
return 0;
}

buf[0] = get_byte();
buf[1] = get_byte();

// assume packet length is big endian
size_t const length = buf[1] || (buf[0] < size )
{
// buffer too small
return 0;
}

// read packet data
for (size_t i = 2; i != length; ++i)
{
buf[i] = get_byte();
}

return length;
}

@Pavel

// assume packet length is big endian
size_t const length = (buf[0] << | buf[1];

Ну вообще, конечно, круто – никто правильно не написал.

> @Tyler функция не реентерабельна

с чего ей быть реентерабельной? )
в условии написано – “Функция recv вызывается на границе пакетов.”.
как вызывающий достигнет этого – ни слова. то ли наша функция должна это делать, то ли будет еще одна go_next_packet().
если не оговорено заранее, то логично писать более короткий вариант, не?

size_t recv(char* buf, size_t size)
{
  unsigned short packSize = (get_byte() << 8)| get_byte();
  if (packSize > size)
  {
    return 0;
  }
  buf[0] = (char)(packSize >> 8);
  buf[1] = (char)packSize;
  unsigned short index = 2;
  while (packSize > index)
  {
    buf[index] = get_byte(3);
    index++;
  }
  return packSize;
}

* This source code was highlighted with Source Code Highlighter.

size_t recv(char *buf, size_t size)
{
if (size < 2)
return 0;
char first_byte = get_byte();
char second_byte = get_type();
unsigned int head = first_byte < size)
return 0;

size_t i = 2;
buf[0] = first_byte;
buf[1] = second_byte;
char byte;
while (i <= head)
{
buf[i++] = get_byte();
}
return head;
}

Часть кода была обрезана

size_t recv(char *buf, size_t size)
{
if (size < 2)
return 0;
char first_byte = get_byte();
char second_byte = get_type();
unsigned int head =
first_byte < size)
return 0;

size_t i = 2;
buf[0] = first_byte;
buf[1] = second_byte;
char byte;
while (i <= head)
{
buf[i++] = get_byte();
}
return head;
}

Не знаю насчет доски, писал в редакторе и не удержался, таки редактировал. Сначала хотел временный буфер сделать, но раз ошибкам неоткуда взяться, не вижу смысла.

#define HEADER_SIZE 2

size_t
recv(
char *buf,
size_t size)
{
char a, /* 1st size byte */
b; /* 2nd size byte */
size_t s, /* data size */
S; /* total size */
char *t; /* temporary buffer */
int i; /* counter */

/* Get size */
a = get_byte();
b = get_byte();
s = a << 8 + b;
S = s + HEADER_SIZE;
/* See if data fits. */
if (size < S)
return 0;
/* Get data. */
buf[0] = a;
buf[1] = b;
for (i = HEADER_SIZE, i < S, i++)
buf[i] = get_byte();
return S;
}

Меня смущает, что get_byte() вроде как не ошибается, но пусть это будет так.

А, ну да, ошибся, конечно Надо съедать пакет при ошибке и раз неизвестна endianness первых двух байтов, неясно, как их интерпретировать.

Ребят, а чего вы все дружно накинулись на get_byte??? По одному байту из сокета сосать? Вы офигели, за такой оверхед расстреливать надо!

read(sock, buf, 2) // получаем длину, причём read нам сразу должен дать правильную endiannes, ибо предполагаем, что посылающая платформа соответствует принимающей

int packet_len = (int)((unsigned short int*)buf)[0]; // пусть компилятор сам разберётся, как он там инты хранит.

if( size < packet_len ) return(0); // Та не лизе, батько! У криньку не лизе!

if( packet_len < 2 ) return(0); // Если длина кривая – ругаемся

int data_len = packet_len – 2;

read(sock, buf + 2, data_len); // дочитываем что положено.

return(packet_len);

Обрамление read на случаи, если датаграмма не дошла целиком и прочитано меньше, чем попросили, писать не стал, ибо в лом.

Точно такая же была у меня на собеседовании в британское подразделение ARM, которое кстати отличалось своей логичностью и правильностью в отличии от майкрософтовского собеседования, потому-что проверяли то точ надо и не было кучи brainfucker-ов, которые у меня активно спрашивали на интервью в Microsoft несмотря на все новые веяния, что их запрещено спрашивать.

Правда в результате таки выбрал Microsoft

Добрый день!
Раз передающая сторона ведёт себя хорошо, значит, порядок байтов будет тоже правильным (это важно для вычисления размера пакета).
Задача хранения излишних данных, не влезающих в буфер, не решена, условие об этом умалчивает. std::vector& на вход помог бы это обойти.
Вот вариант решения
size_t revc( char * buf, size_t size )
{
enum { header_size = 2 };
assert( header_size <= sizeof( size_t ) );

char * p = buf;
size -= header_size;

for ( int i = 0; i data_size ) ? data_size : size;
left > 0;
– left )
{
if ( !( *p++ = get_byte() ) )
return 0;
}

return data_size;
}

PS Как форматировать код?

Вот ссылка на скриншот из текстового редактора:
http://clip2net.com/s/LFRi

char get_byte();

size_t recv(char* buf, size_t size)
{
if (size < 2 || !buf)
return 0;

byte bCur;
int nBytes = 0;
bool blFullPack = false;
while (blFullFack == false)
{
bCur = get_byte();
nBytes++;
if (nBytes = 2)
blFullPack = MAKEDWORD(buf[0], buf[1]) == nBytes;

}

return nBytes;
}

@Алексей Пахунов
Я ж специально написал — “Обрамление read на случаи, если датаграмма не дошла целиком и прочитано меньше, чем попросили, писать не стал, ибо в лом.” Я ж на работе, блин! Мне работать надо, а не задачки решать!

Не удержался от своих двух копеек:

size_t recv(char* buf, size_t size)
{
 if (size < 2)
    return 0;

 unsigned char const len1 = get_byte();
 unsigned char const len2 = get_byte();

 size_t const packet_len = // assuming network order
    static_cast <size_t> (len1) << 8 + static_cast <size_t> (len2);

 size_t const towrite = packet_len < size ? packet_len : size;

 buf[0] = len1;
 buf[1] = len2;

 for (size_t remaining = towrite - 2, i = 2; remaining > 0; --remaining, ++i)
 {
    buf[i] = get_byte();
 }

 return towrite;
}

* This source code was highlighted with Source Code Highlighter.