Click here to Skip to main content
16,016,894 members
Home / Discussions / C / C++ / MFC
   

C / C++ / MFC

 
AnswerRe: Class Shape Pin
_Flaviu23-Jul-17 23:42
_Flaviu23-Jul-17 23:42 
GeneralRe: Class Shape Pin
Richard MacCutchan23-Jul-17 23:58
mveRichard MacCutchan23-Jul-17 23:58 
AnswerRe: Class Shape Pin
Victor Nijegorodov24-Jul-17 22:38
Victor Nijegorodov24-Jul-17 22:38 
GeneralRe: Class Shape Pin
kumn1d25-Jul-17 8:52
kumn1d25-Jul-17 8:52 
QuestionRe: Class Shape Pin
David Crow25-Jul-17 2:23
David Crow25-Jul-17 2:23 
AnswerRe: Class Shape Pin
kumn1d25-Jul-17 8:51
kumn1d25-Jul-17 8:51 
QuestionRe: Class Shape Pin
David Crow25-Jul-17 10:15
David Crow25-Jul-17 10:15 
SuggestionEducational: my buffer scroll C++ working code. Pin
Member 132416522-Jul-17 0:31
Member 132416522-Jul-17 0:31 
Hello. It my first message here, I'll try to do it the right way.

The programming is my hobby (MinGW 32bit). About topic. I would like to represent my C++ code for buffer scroll. Perhaps I designing another bike, but still... What I mean about scrolling. For example, I have some buffer in which data starts somewhere in the middle:
C++
char * buffer = "World!Hello, ";

But I need:
C++
char * buffer = "Hello, World!";

So I need to cut out data at the end, move the rest of data to the end of buffer and paste cutted data to the beginning. This is "lossless buffer scrolling" of what I am talking about.

This is a trivial job if ones use temporary buffer not less than half of the *buffer's length, few memcpy() statements and so on. But this is not my case.

Condition 1. Source buffer size is very large (1/2 or 2/3 of total physical ram). So it is not good idea to allocate temporary buffer.
Condition 2. I can not use data storage like HDD drive. I can not use any kind of swap techniques. (It will produces temporary system freeses.)
Condition 3. I am not what to use virtual addressing techniques to virtually scroll buffer.
Condition 4. The buffer size and scroll distance is arbitrary (sets as function parameters).

So I created a scrolling buffer by permutation, which source code I would like to public. It is quite tested by brutte-force method (buffer size and scrolling distance were alternated, the result is compared with alternative scrolling techniques). In my opinion, the implementation of the method is unusual (or, at least, interesting).


Here it is:
C++
namespace CommonTools
  {
 /// Code by Shepel' Nikolay E., Moscow, Russia, published at 22 July 2017, http://www.codeproject.com.
#ifdef DEBUG
  uint32_t scroll_raw_buffer_last_rounds = 0;
#endif

  void scroll_raw_buffer (void *data , const uint32_t buffer_size, uint32_t distance)
  {
#ifdef DEBUG
    scroll_raw_buffer_last_rounds = 0; // Statistics about rounds...
#endif
    // Для реализации скроллинга необходим двойной запас по размеру буффера,
    // т.е. buffer_size<(UINT_MAX/2) если использовать в функции 32х разрядные
    // переменные, иначе можем выскачить за их максимальный размер, если
    // надо будет буффер сместить влево на 1.

    // WARNING!!!
    // We need double reserve for addressing buffer elements (buffer_size<(UINT_MAX/2)).
    // Otherwise we can get register overflow while scrolling buffer with
    // size>=INT_MAX to the left with distance==1
    if (buffer_size >= INT_MAX)
      throw CommonTools::Errors::Simple (CommonTools::Errors::StE_Overflow, __PLACE__);

    if ( (!data) || (buffer_size < 2)) return;
    distance %= buffer_size;
    if (!distance) return;
    TRAP_in_DEBUG (distance >= buffer_size, msg_interror)

    uint8_t *buf = (uint8_t *) data;
    const uint32_t shift_value = distance;



#ifdef DEBUG
    static const size_t max_stack_buffer = 256;
#else
    static const size_t max_stack_buffer = 1024;
#endif

    // If buffer size is quite small we can use the simplest way...
    if (buffer_size <= max_stack_buffer)
      {
        uint8_t *tmp_buf = (uint8_t *) alloca (buffer_size);
        memcpy (tmp_buf, buf, buffer_size);

        memcpy (buf + shift_value, tmp_buf, buffer_size - shift_value);
        memcpy (buf, tmp_buf + buffer_size - shift_value, shift_value);
        return;
      }

#ifdef DEBUG
    scroll_raw_buffer_last_rounds = 1;
#endif

    uint32_t bytes_left = buffer_size, bytes_per_round = 0;
    uint32_t total_rounds = 0;
    uint32_t round_number = 1; // [1...total_rounds]
    uint8_t  *next_data_buffer = 0;
    uint32_t dest_index;
#ifdef DEBUG
    const uint8_t * const out_of_buffer = buf + buffer_size;
#endif

    do // Starting "merry-go-round"
      {
        {
          const uint32_t round_start_offset = round_number - 1;
          dest_index = round_start_offset;
          if (dest_index >= buffer_size) dest_index -= buffer_size;
          uint8_t next_data = buf[dest_index];
          do
            {
              dest_index += shift_value; if (dest_index >= buffer_size) dest_index -= buffer_size;
              register uint8_t &destination = buf [dest_index];
              swap (destination, next_data);
              bytes_left--;
            }
          while (dest_index != round_start_offset);
        }

        if (!bytes_left) // If it was last round (or the single one) we finish here...
          break;
        if (round_number == 1)
          {
            bytes_per_round = buffer_size - bytes_left;
            total_rounds = buffer_size / bytes_per_round;
#ifdef DEBUG
            scroll_raw_buffer_last_rounds = total_rounds;
#endif
            // The residue of division must be zero !!!
            TRAP_in_DEBUG (buffer_size % bytes_per_round, msg_bogus_state)
          }
        round_number++;

        // If we come here so multiple rounds are required  for scroll operation
        // I think it is because buffer length and distance have common dividors... (I'm not strong in mathematics)
        // We can use some sort of optimisation in this case. We can move blocks of data.
        // The size of such blocks are limited by common dividors mensioned before...

        if (!next_data_buffer) // The temporary buffer for blocks operation.
          next_data_buffer = (uint8_t *) alloca (max_stack_buffer);

        // The code in cycle below is usefull if block_size>1.
        // We check this indirectly by means of condition in "for()" statement below.
        // Otherwise this cycle will be skipped and upper cycle
        // will be used with single byte code.
        for (;round_number  < total_rounds;) //the same condition as if we use "(total_rounds-round_number+1)>1" but less operations are required
          {
            const uint32_t rounds_left = total_rounds - round_number + 1;
            // Activating block move
            const size_t block_size = min_ct (max_stack_buffer, rounds_left);
            const uint32_t round_start_offset = round_number - 1;
            dest_index = round_start_offset;
            if (dest_index >= buffer_size) dest_index -= buffer_size;

            TRAP_in_DEBUG (buf + dest_index + block_size >= out_of_buffer, msg_interror)
            memcpy (next_data_buffer, buf + dest_index, block_size);
            TRAP_in_DEBUG (bytes_left < bytes_per_round*block_size, msg_interror)
            do // block move DO
              {
                dest_index += shift_value; if (dest_index >= buffer_size) dest_index -= buffer_size;
                register uint8_t *destination = buf + dest_index;

/**
        If region to copy overlaps the end of main buffer, special copy
        routine is required (see below).
        But this is never happens, because after the end of the buffer
        the beggining  starts. The beggining element is moved at the
        firstest step in upper cycle. The algo is designed that it is
        impossible if some byte is moved twice.
        So I left this commented (disabled) block (I am not sure that
        it is works good because it is never tested):
**/
/*
                if (destination + block_size > out_of_buffer)
                  {
                    const uint32_t part1 = out_of_buffer-destination;
                    TRAP_in_DEBUG (part1>block_size,msg_interror)
                    memswap (destination,next_data_buffer,part1);
                    const uint32_t part2 = block_size-part1;
                    memswap (buf,next_data_buffer+part1,part2);
                  }
                else
*/
              memswap (destination, next_data_buffer, block_size);
              } // EOF block move DO
            while (dest_index != round_start_offset);
            bytes_left -= bytes_per_round * block_size;
            round_number += block_size;
          } // EOF for (;round_number  < total_rounds;)
      } // Do "merry-go-round"
    while (bytes_left > 0);

    return;
  }

} // namespace CommonTools


Important notes:
1. If ones need negative direction you can use distance=buffer_size-1 as -1 direction.
2. swap() is just variables swapping, min_ct() function returns the minimum value from two arguments.
3. TRAP_in_DEBUG() or TRAP() are macroses to terminate program with message if first parameter is true (message is in 2nd parameter, like ASSERT() but little different way).
4. Function has size limit of scrolling buffer (up to INT_MAX, about 2 Gb in my case).
5. If someone would like to use this code, I will be pleasured if my name is mentioned somewhere in credits..
Echo7


modified 22-Jul-17 11:27am.

GeneralRe: Educational: my buffer scroll C++ working code. Pin
Richard MacCutchan22-Jul-17 0:57
mveRichard MacCutchan22-Jul-17 0:57 
GeneralRe: Educational: my buffer scroll C++ working code. Pin
Member 132416522-Jul-17 5:19
Member 132416522-Jul-17 5:19 
GeneralRe: Educational: my buffer scroll C++ working code. Pin
leon de boer22-Jul-17 1:14
leon de boer22-Jul-17 1:14 
GeneralRe: Educational: my buffer scroll C++ working code. Pin
Member 132416522-Jul-17 5:09
Member 132416522-Jul-17 5:09 
QuestionCN Pin
Member 1332222821-Jul-17 7:58
Member 1332222821-Jul-17 7:58 
AnswerRe: CN Pin
Afzaal Ahmad Zeeshan21-Jul-17 9:12
professionalAfzaal Ahmad Zeeshan21-Jul-17 9:12 
AnswerRe: CN Pin
jeron121-Jul-17 9:34
jeron121-Jul-17 9:34 
AnswerRe: CN Pin
David Crow21-Jul-17 10:30
David Crow21-Jul-17 10:30 
QuestionDoes CString;;GetBufferSetLength Set/Allocate the CString Buffer Pin
ForNow20-Jul-17 15:55
ForNow20-Jul-17 15:55 
AnswerRe: Does CString;;GetBufferSetLength Set/Allocate the CString Buffer Pin
Richard MacCutchan20-Jul-17 20:34
mveRichard MacCutchan20-Jul-17 20:34 
AnswerRe: Does CString;;GetBufferSetLength Set/Allocate the CString Buffer Pin
Jochen Arndt20-Jul-17 21:00
professionalJochen Arndt20-Jul-17 21:00 
GeneralRe: Does CString;;GetBufferSetLength Set/Allocate the CString Buffer Pin
ForNow21-Jul-17 3:05
ForNow21-Jul-17 3:05 
GeneralRe: Does CString;;GetBufferSetLength Set/Allocate the CString Buffer Pin
Richard MacCutchan21-Jul-17 3:24
mveRichard MacCutchan21-Jul-17 3:24 
GeneralRe: Does CString;;GetBufferSetLength Set/Allocate the CString Buffer Pin
Jochen Arndt21-Jul-17 3:35
professionalJochen Arndt21-Jul-17 3:35 
Question《programming game AI by example》 Pin
bestbear19-Jul-17 20:11
bestbear19-Jul-17 20:11 
AnswerRe: 《programming game AI by example》 Pin
leon de boer19-Jul-17 20:51
leon de boer19-Jul-17 20:51 
GeneralRe: 《programming game AI by example》 Pin
bestbear21-Jul-17 2:12
bestbear21-Jul-17 2:12 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.