C++ Array (1)   Leave a comment

A friend asked for a more concrete explanation of a StackOverflow question “Assigning char array a value in C”. Basically, it is about the difference of the following two code snippets:

// 1.
char fast_car[15] = "Bugatti";

// 2.
char fast_car[15];
fast_car = "Bugatti";

The short answer is that:

  • 1 defines an array[10] of char and initializes the first 8 elements to ‘B’, ‘u’, ‘g’, ‘a’, ‘t’, ‘t’, ‘i’, and ‘’. The last 2 elements are not initialized so no assumption should be made about their contents.
  • 2 defines an array[10] of char without initialization (therefore no assumption should be made about their contents), then it tries to assign the char array with “Bugatti”. The assignment triggers a compile time error.

Below is a revisit to C++ array in more depth.

Array Definition

bounded array

In most cases, an array is defined as bounded array:

T a[N];

where, T is the element type, N is the bound of the array. This defines an array object of N elements of T type.

zero-sized array

The C++ standard says that N “shall be an integral constant expression and its value shall be greater than zero” (C++2011 8.3.4/1). What if we try to define a zero-sized array? See this example:

#include <iostream>
int c[0];   // line A: 0-bound array
int main(int, char**)
{
    c[0] = 42;
    std::cout << c[0];
    return 0;
}

Even though gcc 4.9.2 silently builds it (and print out 42), Visual Studio 2013 complains at line A “error C2466: cannot allocate an array of constant size 0”.

Do not use an array of size 0.

unbounded array

If N is omitted in the array definition, it is an array of unknown bound, or, unbounded array.

An unbounded array is an incompletely-defined object type (C++2011 3.9/5), which is an incomplete type (other incomplete types include: a class that has been declared but not defined, an array of incomplete element type, and void). Basically, an incomplete type has unknown size, therefore no object shall be defined to have an incomplete type.

#include <iostream>
int c[];    // line A: unbound array
int main(int, char**)
{
    c[0] = 42; // line B
    std::cout << c[0];
    return 0;
}

gcc 4.9.2 generates a compile error “error: storage size of ‘c’ isn’t known” at line A.

Visual Studio 2013 compiles fine, but generates a link error “error LNK2001: unresolved external symbol "int * c" (?c@@3PAHA)”. Basically, at compile time VS2013 knows c is an unbounded array and in line B array c decays to a int pointer, so line B becomes *c = 42. However, VS2013 does not generate actual object for the unbounded array in object file, so this results in the link error.

Incomplete Array Types

To be really useful, an incomplete type (other than void) needs to be completed. The completion of incomplete types is given in C++2011 3.9/6.

incomplete class type

A declared incomplete class type can be completed in a translation unit later by providing the class definition. The declared and complete types are the same type. That’s how forward declaration works. See this example:

class X;    // incomplete class type
X* p;       // p is pointer to incomplete class type X: ok

void foo()
{
    p++;    // line A: ill-formed !
}

class X {}; // now X is defined and completed

void bar()
{
    p++;    // increment pointer to complete class type X: ok
}

C++ compilers complain at line A, because at the point X is incomplete and its size is unknown, so there is no way that the compiler can increment a pointer to X.

incomplete bounded array of incomplete element type

Similar to incomplete class type, a bounded array of incomplete element type can be completed in a translation unit later by providing the definition of incomplete element type. The declared and complete bounded array types are the same type. See this example:

class X;            // incomplete class type
using X10 = X[10];  // incomplete bounded array due to incomplete element type
X10* p;             // p is pointer to incomplete bounded array X10: ok

void foo()
{
    p++;    // line A: ill-formed !
}

class X {}; // now X is defined and completed, so is X10

void bar()
{
    p++;    // increment pointer to complete class type X: ok
}

incomplete unbounded array

An unbounded array (of complete element type) is incomplete, and a distinct type from any of the bounded array types of the same element.

#include <type_traits>

using IntU = int[];     // incomplete unbounded array type
IntU* p;                // p is pointer to incomplete unbounded array type: ok

void foo()
{
    p++;                // line A: ill-formed !
}

static_assert(!std::is_same<IntU, int[1]>::value, "Oops");  // line B
static_assert(!std::is_same<IntU, int[2]>::value, "Oops");  // line C
using IntU = int[10];   // line D: ill-formed !

In above code, Line A does not compile because IntU is incomplete and of unknown size as usual. Line B and C show that incomplete unbounded int[] is a distinct type from complete bounded int[N]. Line D may try to complete IntU but in vain. Due to the fact that int[] and int[10] are two distinct types, Line D results in redefinition error for IntU.

Although the incomplete unbounded array type itself cannot be completed later, the unbounded array type of a declared object can be completed later by providing the definition of the object with bound. See example:

using IntU = int[];     // incomplete unbounded array type
extern IntU a;          // the type of a is incomplete unbounded array: ok
                        // or use:  extern int a[];
IntU* p;                // p is pointer to incomplete unbounded array type: ok

void foo()
{
    p = &a;             // line A: ok
    //p++;              // line B: ill-formed !
}

int a[10];              // line C: provide definition of object a

int main(int, char**)
{
    return 0;
}

Line A above is okay because it does not involve the size of object a of incomplete type. Line B does not compile if uncommented as usual. Line C provides the definition of extern object a, as well as completes the type of object a. Without Line C the program cannot link. This program builds with both gcc and VS2013.

This is another example:

using IntU = int[];     // incomplete unbounded array type
extern IntU a;          // the type of a is incomplete unbounded array: ok
                        // or use:  extern int a[];
IntU* p;                // p is pointer to incomplete unbounded array type: ok

void foo()
{
    p = &a;             // line A: ok
    //p++;              // line B: ill-formed !
}

int a[10];              // line C: provide definition of object a, and completes type of a.

void bar()
{
    p = &a;             // line D: ill-formed !
}

Compare Line A and Line D. Line A is okay because p is pointer to incomplete type IntU, where a is declared as object of IntU. Line C completes the type of object a to be int[10], but it does not complete the type IntU. Starting at this point, IntU differs from the type of a. Line D does not compile, because IntU cannot be completed and remains int[], while a’s type is int[10].

Unbounded and Zero-sized Array in Class

Up to now, it is quite clear that unbounded and zero-sized arrays are something that you should avoid in most cases.

Sometimes you may still see they are used in a class/struct, such as in this StackOverflow question. Below is an example:

struct X
{
    int num;
    char a[];   // line A: unbounded array member
};

static_assert(sizeof(X)==sizeof(int), "Oops");     // line B

struct Y
{
    int num;
    char a[0];  // line C: zero-sized array member
};

static_assert(sizeof(Y) == sizeof(int), "Oops");   // line D

int main(int, char**)
{
    X a, b{ 42 };
    a = b;

    Y c, d{ 42 };
    c = d;

    return 0;
}

The program above builds and runs without problem with both gcc and VS2013, although VS2013 generates warnings for Line A and C: “warning C4200: nonstandard extension used : zero-sized array in struct/union: Cannot generate copy-ctor or copy-assignment operator when UDT contains a zero-sized array”.

Obviously, the real use of the unbounded/zero-sized array in the struct is not to hold 0 elements. The struct is a simulation of array of dynamic size, i.e., size is only known at run time. In such use, num is the number of elements, and a is the seeming buffer to hold the elements. Since Line B and D indicate that the struct does not really have storage for the array, allocating actual buffer of sizeof(X)+num*sizeof(char) bytes to hold struct and elements is user responsibility. X::a or Y::a just provides superficial array access.

The code above is not exactly standard conforming. Compilers support this for historic reasons not to break C legacy code. In fact, if we move the array member from the end of struct to somewhere else:

struct X
{
    char a[];   // line A: unbounded array member
    int num;
};

static_assert(sizeof(X)==sizeof(int), "Oops");     // line B

struct Y
{
    char a[0];  // line C: zero-sized array member
    int num;
};

static_assert(sizeof(Y) == sizeof(int), "Oops");   // line D

int main(int, char**)
{
    return 0;
}

Although gcc still builds it, VS2013 now generates errors for Line A and C: “error C2229: struct ‘X’/’Y’ has an illegal zero-sized array”.

In C, another popular workaround for array of dynamic size is to use array of size 1, like:

struct X
{
    int num;
    char a[1];  // line A
};

Now line A is completely conforming to the standard. But of course, hacking is necessary to enable accessing other elements of the array through X::a.

In C++, we have the standard library with different kinds of containers. We should not use such hacks. Just use appropriate containers that support dynamic size, for example, std::vector.

Array Initialization

When an array is defined, maybe it is not initialized:

T a[10];

This does not mean a has arbitrary garbage in its elements. Depending on what T type is, the element objects in a are accordingly constructed. For fundamental types, such as int and char, the elements are random bytes practically, for efficiency reasons. The class types, the elements are default constructed – this means that T must have default constructor.

initialization of array of explicit bound

You can also choose to initialize the array when defined:

int a1[3] = { 1, 2, 3 };    // full initialization
int a2[3] = { 1, 2 };       // partial initialization, a1[2] not initialized
int a3[3] = { 1, 2, 3, 4};  // compile error: too many initializer values

int a4[3]{ 1, 2, 3 };       // full initialization
int a5[3]{ 1, 2 };          // partial initialization, a1[2] not initialized
int a6[3]{ 1, 2, 3, 4 };    // compile error: too many initializer values

initialization of array of implicit bound

A bounded array can be defined without explicitly giving the bound if it is initialized:

#include <type_traits>
int a[] = { 1, 2, 3 };
static_assert(std::is_same<decltype(a), int[3]>::value, "Oops");
static_assert(sizeof(a) == sizeof(int[3]), "Oops");
int b[3];
static_assert(std::is_same<decltype(a), decltype(b)>::value, "Oops");

The static_assert lines show that a is in fact bounded array with size matching the number of initializer values, even it looks like an unbounded array. Using this technique can avoid mismatching bound and number of initializer values.

No matter explicit or implicit bound, if the array is in global/namespace scope, the initialization has no run-time cost because loader takes care of it. If the array is in a local scope (such as in a function), the array has to be constructed and initialized at run time, and the elements are populated at run time with CPU cycles.

initialization of char array

Similar to above, a char array can be initialized with char values:

char a1[3] = { 'A', 'B', 'C' }; 
char a2[]  = { 'A', 'B', 'C' }; // a2 is char[3] type

In addition to the initializer list, a char array can also be initialized with a string literal:

#include <type_traits>
#include <cassert>

char a1[4] = { 'A', 'B', 'C', '\0' }; 
char a2[4] = "ABC"; // "ABC" is equivalent to { 'A', 'B', 'C', '\0' }
char a3[]  = "ABC";

static_assert(std::is_same<decltype(a2), decltype(a3)>::value, "Oops");

int main(int, char**)
{
    assert(a2[3] == '\0');
    assert(a3[3] == '\0');
    return 0;
}

This special treatment is useful, because writing string literal is much easier than writing the initializer char values in the code when the string is long. Just remember that a string literal has an invisible terminating null char, and make sure the char array bound is big enough. Better yet, use the char array of implicit bound to avoid mismatching, especially when you may need to change the string literal (and its length) in the future.

Array Assignment

Finally we get close to the original question: instead of defining a char array with string literal initialization, can we separate the definition and initialization, i.e., define the array first then assign to it a string literal?

The second code snippet obviously must not live in the global or namespace scope, so let’s put it in a function, for example:

void foo()
{
    char fast_car[15];    // line A
    fast_car = "Bugatti"; // line B
}

If we try to compile it, both gcc and VS2013 generates error on Line B: “error ‘=’ : cannot convert from ‘const char [8]’ to ‘char [15]’”. From here it is also obvious that a string literal is of type const char[N] in the context.

Following the error message, let’s modify the code to use a matching bound:

void foo()
{
    char fast_car[8];     // line A
    fast_car = "Bugatti"; // line B
}

But Line B still does not compile. gcc complains “error: invalid array assignment”. VS2013’s error is different: “error C2440: ‘=’ : cannot convert from ‘const char [8]’ to ‘char [8]’”.

Trying to please VS2013, let’s modify the code again so it has no such excuse:

void foo()
{
    char fast_car[8];     // line A
    char slow_car[8] = "Bugatti";
    fast_car = slow_car; // line B
}

At Line B, slow_car is also ‘char [8]’ type. Now VS2013 says “error C2106: ‘=’ : left operand must be l-value”. gcc still reports the same error on Line B: “error: invalid array assignment”.

The real problem is that C++ says, “Objects of array types cannot be modified, see 3.10” (C++2011 8.3.4/5). Even if you can get lvalue of the array object, you still cannot modify the array (C++2011 3.10/9).

Of course, by saying that, the standard does not mean that you cannot modify the individual elements of an array. It just means that you cannot modify the array object as a whole, for example, you cannot assign another array (even of the exact same type) to it. No array assignment is allowed.

However, this is an example that seems contrary to that:

#include <iostream>
#include <cstring>

struct X
{
    char a[4];
};

int main(int, char**)
{
    X x;
    std::strcpy(x.a, "ABC");
    X y;
    y = x;  // line A
    std::cout << y.a;   // print: ABC
    return 0;
}

Why does the program print out “ABC”, if at Line A array x.a is not assigned to array y.a?

Notice that the struct X above is the same as this struct X, which also works in the program above:

struct X
{
    char a[4];
    X& operator = (const X& other) = default;
};

Now, as you can expect, if you want to define the copy assignment operator of X as follows:

struct X
{
    char a[4];
    X& operator = (const X& other)
    {
        a = other.a;  // line A
        return *this;
    }
};

Line A would give you trouble because you want to assign to the array.

The default compiler-generated copy assignment operator of X is more or less like this (which compiles fine because no array is assigned):

struct X
{
    char a[4];
    X& operator = (const X& other)
    {
        for (size_t i = 0; i < 4; ++i)
            a[i] = other.a[i];
        return *this;
    }
};

In other words, the compiler performs per-element copy assignment rather than assignment of array as a whole in the default copy assignment operator for a class containing an array. Compiler needs to do this to make sure classes with array members can be assigned.

From the example, you can also see that, if you want to have the effect of assignable array, you can wrap the array within a struct, and use the struct instead, without even implementing the copy assignment operator.

It seems this post is getting too long. I will leave other topics about array to another post. Specifically, it will need to cover array decaying to pointer to first element, array parameter in function, reference to array, and so on.

Find The Number That Does Not Appear Exactly N Times In An Array   1 comment

Just for fun.

Problem Template: In an integer array, all the unique numbers appear exactly N times, except one number which appears less than N times (but more than 0 times). Find that number.

An actual problem uses a specific given N. For example, N=2, or 3, or 4 is most common. N cannot be 1, because the number to be found would appear 0 times – contradicting with the problem.

N = 2

This is the basic problem. In this problem, all numbers appearing twice other than the target number to be found, which appears once. There is a simple solution to this problem. Just accumulate-XOR the elements, the numbers appearing twice cancel out, and the remaining result is the target number.

N = 4

N = 4 is harder. Let’s assume the target number appears k times (k=1, 2, or 3).

If k = 1 or k = 3, it is very easy because it can be solved the same as N = 2, as those numbers appearing even number of times would cancel out.

However, if k = 2, it is not that simple, because using the same approach would cancel out the target number as well, resulting an incorrect 0 all the times.

A revisit of the N = 2 problem would reveal that XOR is in fact performing the modulo-2 addition for each bit independently. If we perform the modulo-4 addition for each bit independently, all those numbers appearing 4 times would result in sum 0, and the final sum would be the sum of target number of k times, which we can simply divide it by k to get the target number.

The per-bit calculation is as follows. Since N = 4, we need two bits to represent the accumulation result of each bit. Let the lower bit be sum and higher bit be carry. Below is the table of the new sum and carry bits for a new addend:

carry      0 0 0 0 1 1 1 1
sum        0 0 1 1 0 0 1 1
addend     0 1 0 1 0 1 0 1
--------------------------
sum_new    0 1 1 0 0 1 1 0
carry_new  0 0 0 1 1 1 1 0

A simple observation is that sum_new = sum ^ addend, carry_new = carry ^ (sum & addend). When all the per-bit modulo-4 additions are done, the accumulation result is in (carry, sum) for each bit. Because each bit of carry means 2, carry should be multiplied with 2 then added to sum to yield the correct accumulation result. The code is as follows:

// N = 4 
// int A[n]
int findNon4Number(int A[], int n) 
{
    int sums = 0;
    int carries = 0;
    
    for(int i=0; i<n; ++i)
    {
        // per-bit modulo_4 addition
        carries = carries ^ (sums & A[i]);  // carry bit
        sums = sums ^ A[i];                 // low bit
    }
    sums += (carries<<1);   // real sum
    
    int k = n%4;
    assert(sums%k == 0);
    return sums / k;
}

N = 3

Similar to N = 4, N = 3 resorts to how to perform per-bit modulo-3 additions. Below is the table:

carry      0 0 0 0 1 1
sum        0 0 1 1 0 0
addend     0 1 0 1 0 1
----------------------
sum1       0 1 1 0 0 1  // temporary, before mod_3
carry1     0 0 0 1 1 1  // temporary, before mod_3
sum_new    0 1 1 0 0 0  // after mod_3
carry_new  0 0 0 1 1 0  // after mod_3

The code is:

// N = 3
// int A[n]
int findNon3Number(int A[], int n) 
{
    int sums = 0;
    int carries = 0;
    
    for(int i=0; i<n; ++i)
    {
        //// per-bit modulo_3 addition
    	int sum1 = sums ^ A[i];              // low bit
    	int car1 = carries | (sums & A[i]);  // carry bit
        // modulo_3: clear both bits if they are both 1:
    	sums = sum1 & (~(sum1 & car1));
    	carries = car1 & (~(sum1 & car1));
    }
    sums += (carries<<1); // real sum
    
    int k = n%3;    // number of the non-3 number
    assert(sums%k == 0);
    return sums / k;
}

It is a little bit more complex than that of N = 4, but not too much.

Put Together

The complete code with a few simple tests is as follows:

#include 
#include 

// N = 4 
// int A[n]
int findNon4Number(int A[], int n) 
{
    int sums = 0;
    int carries = 0;
    
    for(int i=0; i<n; ++i)
    {
        // per-bit modulo_4 addition
        carries = carries ^ (sums & A[i]);  // carry bit
        sums = sums ^ A[i];                 // low bit
    }
    sums += (carries<<1);   // real sum
    
    int k = n%4;
    assert(sums%k == 0);
    return sums / k;
}

// N = 3
// int A[n]
int findNon3Number(int A[], int n) 
{
    int sums = 0;
    int carries = 0;
    
    for(int i=0; i<n; ++i)
    {
        //// per-bit modulo_3 addition
    	int sum1 = sums ^ A[i];              // low bit
    	int car1 = carries | (sums & A[i]);  // carry bit
        // modulo_3: clear both bits if they are both 1:
    	sums = sum1 & (~(sum1 & car1));
    	carries = car1 & (~(sum1 & car1));
    }
    sums += (carries<<1); // real sum
    
    int k = n%3;    // number of the non-3 number
    assert(sums%k == 0);
    return sums / k;
}

int main() 
{
    {
        int A1[] = {3,3,3,4,3};
        int A2[] = {9,5,5,9,9,9};
        int A3[] = {6,7,6,7,6,7,7,8,8,8,8};
        std::cout << findNon4Number(A1, sizeof(A1)/sizeof(int)) << std::endl; // 4
        std::cout << findNon4Number(A2, sizeof(A2)/sizeof(int)) << std::endl; // 5
        std::cout << findNon4Number(A3, sizeof(A3)/sizeof(int)) << std::endl; // 6
    }
    
    {
        int A1[] = {3,3,3,7};
        int A2[] = {9,8,8,9,9};
        int A3[] = {6,7,6,7,6,7,9,9};
        std::cout << findNon3Number(A1, sizeof(A1)/sizeof(int)) << std::endl; // 7
        std::cout << findNon3Number(A2, sizeof(A2)/sizeof(int)) << std::endl; // 8
        std::cout << findNon3Number(A3, sizeof(A3)/sizeof(int)) << std::endl; // 9
    }
    return 0;
}

As simplified code to show the basic idea, the sums += (carries << 1) code line does not check the overflow condition. It also assumes k is not 0.

Conclusion

The key is to perform modulo-N addition/accumulation per-bit independently, which requires ceiling(log_2(N)) bits for each bit of accumulation. These bits can be represented in separate ceiling(log_2(N)) integers. For N = 3 or 4, the space requirement is only 2 integers to represent the accumulation, no matter how big n is. If N is bigger, more integers are needed for storage; and the per-bit addition will be a little more complex. Although it may seem twisted in the per-bit addition, it is simply expanded form of addition in binary format with modulo operation.

Overall this approach is very efficient. For given N<<n, the space requirement is O(1) and time requirement is O(n).

Posted April 17, 2015 by binglongx in C++

Tagged with

read_buffer and read_1024   Leave a comment

Just for fun, below is an implementation for the read_buffer problem. The problem asks for an implementation of a function that reads chars to a user provided buffer of arbitrary size, using an already implemented buffer reading function, which however can only read to a buffer of fixed size (1024 in this example).

First Implementation

#include <cstring>      // std::memcpy
#include <algorithm>    // std::min

// read up to 1024 chars into buf. return number chars actually written into buf.
// if return value is less than 1024, the source underneath is exhausted at this time.
size_t read_1024(char* buf);    // implemented elsewhere.

// just a better name for the constant 1024
const size_t BUF_LEN = 1024;

// read to user provided buf of at most buf_len chars. return number chars actually written into buf.
size_t read_buffer(char* buf, size_t buf_len)
{
    static char s_buf[BUF_LEN]; // cache for read_1024.
    static size_t s_offset = 0; // unread chars start here in cache.
    static size_t s_count = 0;  // number of unread chars in cache.

    // policy-dependent. you may want it to crash for nullptr instead of guarding against this.
    if (nullptr == buf)
        return size_t(0);

    size_t total_read_count = 0;// how many chars already read into buf
    bool exhausted = false;     // if source of read_1024 is exhausted and no more chars available
    while (total_read_count < buf_len)
    {
        if (s_count>0)
        {   // if there are left over unread chars in cache, use those first.
            size_t copy_count = (std::min)(buf_len - total_read_count, s_count);
            std::memcpy(buf + total_read_count, s_buf + s_offset, copy_count);
            total_read_count += copy_count;
            s_offset += copy_count;
            s_count -= copy_count;
            if (exhausted)
                break;  // exhausted. stop.
        }
        else
        {   // now must read afresh using read_1024
            if (buf_len - total_read_count >= BUF_LEN)
            {
                // all chars can go to user buffer directly bypassing cache
                size_t read_count = read_1024(buf + total_read_count);
                total_read_count += read_count;
                if (read_count < BUF_LEN)
                    break;  // exhausted. stop.
            }
            else
            {
                // must use cache, or it may write beyond user buf boundary
                size_t read_count = read_1024(s_buf);
                s_offset = 0;
                s_count = read_count;
                if (read_count < BUF_LEN)
                {
                    exhausted = true;
                    if (read_count == 0)
                        break;  // exhausted and nothing in cache. stop.
                    // otherwise, let it read from left over cache, in code above.
                }
            }
        }
    }
    return total_read_count;
}

The read_buffer function implemented above:

  • it reads properly if user buffer is equal to or larger than 1024 chars;
  • it reads properly without buffer overflow if user buffer is less than 1024 chars;
  • no chars are lost between read_buffer calls.

Refactored Implementation

This is a little bit refactored version that puts code around cache into a class template buffer_cache, such that the read_buffer code is clearer:

#include <cassert>      // assert
#include <cstring>      // std::memcpy
#include <algorithm>    // std::min

// cache object
// Size_:       the fixe size of cache
// FixedReader: the function to fill fixed cache
template<size_t Size_, size_t(*FixedReader)(char*)>
struct buffer_cache
{
    static const size_t Size = Size_;

    // user can call fixed reader directly
    static size_t read_raw(char* buf) { return FixedReader(buf); }

    // construct an empty cache
    buffer_cache() : count_(0) {}

    // if cache is empty
    bool empty() const { return count_ == 0; }

    // read cache and write user provided buffer. return chars written.
    size_t read(char* buffer, size_t len)
    {
        size_t copy_count = (std::min)(len, count_);
        std::memcpy(buffer, buf_ + offset_, copy_count);
        count_ -= copy_count;
        offset_ += copy_count;
        return copy_count;
    }

    // try to fill cache using the fixed reader. return chars filled.
    size_t try_fill()
    {
        assert(empty());
        size_t read_count = FixedReader(buf_);
        if (read_count>0)
        {
            count_ = read_count;
            offset_ = 0;
        }
        return read_count;
    }

private:
    size_t	count_;     // number of unread chars in cache.
    size_t  offset_;    // unread chars start here in cache.
    char 	buf_[Size]; // cache
};

// read up to 1024 chars into buf. return number chars actually written into buf.
// if return value is less than 1024, the source underneath is exhausted at this time.
size_t read_1024(char* buf);

// read to user provided buf of at most buf_len chars. return number chars actually written into buf.
size_t read_buffer(char* buf, size_t buf_len)
{
    using BufferCache = buffer_cache<1024, read_1024>; // only need to change to other size here
    static BufferCache s_cache;

    // policy-dependent. you may want it to crash for nullptr instead of guarding against this.
    if (!buf)
        return size_t(0);

    size_t total_read_count = 0;// how many chars already read into buf

    // first pick up cache chars left over by last call.
    if (!s_cache.empty())
        total_read_count += s_cache.read(buf, buf_len);

    while (total_read_count < buf_len)
    {
        if (buf_len - total_read_count >= BufferCache::Size)
        {
            // all chars can go to user buffer directly bypassing cache, since it's big enough
            size_t read_count = BufferCache::read_raw(buf + total_read_count);
            total_read_count += read_count;
            if (read_count < BufferCache::Size)
                break;  // source exhausted.
        }
        else
        {
            // must use cache, or it may write beyond user buffer boundary
            s_cache.try_fill();
            total_read_count += s_cache.read(buf + total_read_count, buf_len - total_read_count);
            break;  // 
        }
    }
    return total_read_count;
}

Compared to the previous version, it is easy to change the buffer length from 1024 to others in one line where BufferCache is aliased.

Test Code

Below is a simple test program.

#include <cassert>
#include <cstring>
#include <algorithm>

#include <vector>
#include <cstdlib>
#include <iostream>

// simulating the source of chars:
std::vector<char>   g_storage;
size_t              g_pos;

size_t read_1024(char* buf)
{
    size_t count = 1024;
    if (g_pos + count > g_storage.size())
        count = g_storage.size() - g_pos;
    if (count>0)
    {
        std::memcpy(buf, &g_storage[g_pos], count);
        g_pos += count;
    }
    return count;
}

// you need to implement this function:
size_t read_buffer(char* buf, size_t buf_len);

bool test(size_t len)
{
    // generate test data stream.
    g_pos = 0;
    g_storage.clear();
    g_storage.reserve(len);
    for (size_t i = 0; i < len; ++i)
        g_storage.push_back((char)(std::rand() % 256));

    // make a copy of data stream as ground truth.
    std::vector<char> truth = g_storage;

    // to make a few read_buffer() calls with random sizes until the stream is exhausted.
    size_t base = len / 10; // rough read size.
    if (base < 512)
        base = 512;
    std::vector<char> read_chars;   // user buffer
    read_chars.resize(len + 1);
    size_t read_count = 0;
    while (true)
    {
        size_t rc = std::rand() % base;
        if (rc < 1)
            rc = 1;
        size_t rr = read_buffer(&read_chars[read_count], rc);
        std::cout << "    try to read = " << rc << ", actual read = " << rr << "\n";
        read_count += rr;
        if (rr == 0 || rr < rc)
            break;  // exhausted, no more chars to read.
    }

    bool ok = false;
    if (read_count != len)
        std::cout << "  FAIL: mismatch read size: expected=" << len << ", actual=" << read_count;
    else
    {
        read_chars.resize(read_count);
        if (read_chars != truth)
            std::cout << "  FAIL: mismatch read contents";
        else
        {
            std::cout << "  OK. stream matching, size = " << read_count;
            ok = true;
        }
    }
    return ok;
}

int main(int argc, char* argv[])
{
    size_t repeat = 10;
    size_t test_sz[] = { 0, 11, 522, 1024, 3001, 9273, 89704, 123458, 334526 };
    for (size_t i = 0; i < repeat; ++i)
    {
        for (size_t j = 0; j < sizeof(test_sz) / sizeof(test_sz[0]); ++j)
        {
            size_t sz = test_sz[j];
            std::cout << "Test stream size = " << sz << "\n";
            bool ok = test(sz);
            std::cout << std::endl;
            if (!ok)
                return -1;
        }
    }
    return 0;
}

Plug in read_buffer implementation, the test program can check if the implementation is good.

Please note that the code above is not safe in multi-threading use, because it uses static variable to hold cached chars without protection.

Posted March 1, 2015 by binglongx in C++

Tagged with , , , , , , ,

Reinstall Google Play on Motorola DEFY XT for Republic Wireless   1 comment

My Motorola DEFY XT for Republic Wireless crashed yesterday. It would freeze right after booting when it showed “Contacting Network …”. If I remove the SD card, it booted normally. I inserted into the phone again it did not boot. I inserted the SD card into my PC, and PC could initially see the drive, but copying files out of it was extremely slow (like 5KB/s) and finally hung. The SD card was faulty, and I could not recover some useful files, such as downloaded files.

DEFY XT has very limited 388MB Internal storage (i.e., /data). The Internal storage is used to store user installed apps (apks), and user specific data files for system and user apps. The user app apks can be found in the /data/app directory. The data files associated with apps can be found in /data/data/<apk_name>. For example, more than 100MB was used for WeChat data in /data/data/com.tencent.mm, including chat history and others. /data/dalvik-cache can take a lot of space too, as it houses the dex files for the apps. Some of the dex files can be removed to save some space. For example, I deleted the dex file for Google+ because I did not use Google+ on the phone. It is easy to browse around if you have ES File Explorer installed. In the end, it is quite easy to get “insufficient space” error when trying to install more apps. I installed Link2SD and an SD card with 2nd partition to offload apks to the SD card, so I was able to install quite some apps on the phone.

Now that the SD card was gone, a lot of offloaded apps on my phone could not run, because the Link2SD linked apks were no longer accessible from the phone. To accommodate the big data footprint of WeChat, I had even linked Google Play Services and Google Play Store. The trouble was that without Play Store, I could not reinstall other missing apps!

Initially I thought Link2SD moved the Play Store app in /system/app. If the apk was removed from system partition, even factory reset would not be able to revive it, see Factory Reset what is it, and why would you.

Luckily I had another DEFY XT phone with almost the same configuration. Play Store worked fine on that phone, so I was able to download and install ES File Explorer easily. Using ES File Explorer itself, I copied its own apk file to the problematic phone. I could run ES File Explorer on both phones and compare the apk files side by side.

It was easy to find out that the stock Play Store in DEFY XT is /system/app/Phonesky.apk. However the faulty phone had the same apk at the same location. Obviously this was not used. Then I looked at /data/app. Here I saw the difference. The good phone had a newer Play Store /data/app/com.android.vending-2.apk (11.16MB); while the other one had a dummy 0-byte /data/app/com.android.vending-1.apk, which was a symbolic link to actual apk on SD card 2nd partition managed by Link2SD (now non-existing). I also found Google Play Services /data/app/com.google.android.gms-2.apk (27.64MB) on the good phone, which I assumed necessary for Google Play to work.

The next step was simple. I just copied the two apk files from the good phone to the crippled one, and installed them. Launching Play Store right after installation did not work (“application stopped unexpectedly”), but a reboot fixed the problem. I think it should also work if I download the Play Store apk off the internet, see How to download & install the Google Play Store manually.

With Play Store recovered, I was able to install more apps and fix other problems in the phone.

Reference:

How To Install Any App As A System App On Android [Guide]

SM-22301 Shower Radio User Manual   Leave a comment

I cannot find the user manual of SM-22301 Shower Radio over the internet, so I post a scan here.

image

Posted February 21, 2015 by binglongx in Home

Tagged with , , , , ,

Dropbox Referral Program For 500MB Extra Free Bonus Space   Leave a comment

Dropbox is a cloud storage service. It is like a remote online drive that you can put your files there. It is slower than your local hard drive, but it is super reliable. A basic personal account is free to open, and it has 2GB free space.

I have been using Dropbox for quite a few years. There are many nice features of it. For me, the most convenient feature of Dropbox is automatic uploading of photos that I take on my mobile phone. I just install the Dropbox app on my Android phone, and set up the automatic uploading. Whenever I take a picture, it would be backed up to my online Dropbox account automatically. It saved a lot of photos when my microSD card in my phone went wrong some time ago.

If you open an account at Dropbox right now, you get 2GB free space. However, if you create a Dropbox account through a referral link from an existing Dropbox user, you will get extra 500MB space, i.e., 2.5GB total free space. The existing user will also get 500MB extra space for free.

If you so happen to need a Dropbox account, you can use my referral link https://db.tt/4WHpE8bR. To get the 500MB extra space, you need to:

  • Use the referral link to create a new Dropbox account; and
  • Install the Dropbox desktop application on a Windows, Linux or Mac computer; and
  • Sign in to the installed application with the newly created Dropbox account.

That’s it. You will see 2.5GB (instead of 2.0GB) space available in your Dropbox account. And thanks, this will also add 500MB to my Dropbox account. If you need more space, you can publish your referral link to earn bonus space.

Please note that, for this to work, you have to install the Dropbox desktop application on a desktop computer. Installing the Dropbox app on your Android or iOS phone or tablet does NOT qualify for the referral program.

For details, you can also check with Dropbox Referral Program.

Megacubo: A Broadcast Tuner Application on Windows   Leave a comment

Megacubo is featured as the Staff Pick project of February 2015 at SourceForge. The Windows application allows users to watch hundreds of live TV channels and listen to many radio stations on a PC with internet connection.

Excited to learn this in my SourceForge February newsletter, I headed to SF to download and install the application. After downloading megacubo_setup_f.exe, I was really surprised by the way the installer looks. It basically wants to install a lot of fishy bloatware. I checked its SourceForge reviews. It received straight 1-star negative reviews in past 2 months, mostly complaining attempts to install bloatware and language issues.

It is however unfair as I find out that Megacubo is not that bad. The installations of bloatware can be declined during Megacubo setup without affecting the functionalities of the installed application. With some help from free online tools on the internet, I was able to navigate in Megacubo and turn the Portuguese UI into English. Below is a summary.

Install Bloatware-Free Megacubo

The key here is to read each page carefully, and decline the bloatware offers in the installation process, even though sometimes the Decline button may not be very obvious.

Megacubo Setup Wizard shows the Welcome window:

image

Click “Next”, it shows the License Agreement window:

image

Click “Accept”, it now asks if you want to install Binkiland Browser.

image

Most people would believe this is bloatware. Click “Decline” at the bottom left corner. It now asks if you want to install Optimizer Pro.

image

Again I think Optimizer Pro is unnecessary for most people. Choose “Decline”. Finally, it starts to install Megacubo:

image

Turn UI Language From Portuguese To English

When Megacubo runs for the first time, it shows a message box to let you choose Yes or No. The problem is that the message is in Portuguese and I do not know any Portuguese. Worse, the text is not selectable, so I cannot copy it and use Google Translate.

This was what I did. I capture the window while it is on focus using Alt-PrtScrn (a Windows feature), then paste the captured image to IrfanView. In IrfanView, I cropped the text portion of the window. I did not take a snapshot of the message box window, but this was the text portion of that window:

image

I saved that portion to a .jpg file on my local hard drive. Then I used online Free OCR tool to convert the image into Portuguese text, which was:

Deseja ativar o "Controle dos Pais"?
Com o "Controle dos Pais" você pode configurar uma senha
que passará a ser pedida sempre que qualquer usuário_acessar qualquer
conteúdo inadequado para menores. Respondendo NAO os canais com
conteúdo adulto abriram livremente sem pedir senha para acesso.

This was relatively easy job for any OCR tool as the input image was perfectly distortion and noise free. Now Google Translate took it and translated into English:

Want to activate the "Parental Control"?
With the "Parental Controls" you can con fi gure a password
which will be requested whenever any usuário_acessar any
adult content. Responding NOT channels with
adult content freely opened without asking password for access.

From here it is obvious what you want to do with the Yes or No choice. In fact, below is the same message box in English (just that you will not see the English version in most situations):

image

After you dismiss the message box, you arrive at the main UI of Megacubo. It is however Portuguese:

image

If you are like me, and don’t read Portuguese, you want to change to use the English UI. Click the Settings icon and choose the Language menu item:

image

In the dialog box, choose “English”:

image

Megacubo will restart and show the English UI! See below:

image

Choose TV/radio channels here:

image

And you can also see the Options | Change Language menu item that was used above, the English version (in case you want to go back to Portuguese…):

image

When watching TV, sometimes there are Portuguese ads popup windows blocking the TV contents. Normally, you can click the “Fechar e tocar” button on the ads window to dismiss it (according to Google Translate, it means “close and touch”, I bet it is just “click to close”).

Conclusion

It is possible to install Megacubo without any bloatware, and use it with its English UI. As a free TV application, Megacubo has decent quality on the channels that I tried.

However, a lot of TV channels and radio stations in Megacubo are Portuguese. Sometimes when you quit Megacubo, it may fire up a marketing web page in your default web browser – not a big problem for me.

Follow

Get every new post delivered to your Inbox.

Join 47 other followers