Binglong's space

Random notes on computer, phone, life, anything

Archive for February, 2025

Migrate To A New iPhone

Posted by binglongx on February 8, 2025

After you buy a new iPhone or otherwise get a different fresh iPhone, you will need to smoothly move the data from your current iPhone to this new iPhone. Apple Quick Start makes this very easy.

Important: Before you start, make sure your current iPhone is using the latest iOS to reduce the change of migration failure. You can do so by go to Settings -> General -> Software Update. You don’t need to worry about the new iPhone: If the new iPhone does not have latest iOS, it may automatically perform software update in the early stage of migration, for example after it gets WiFi connnection information from your current iPhone.

You can migrate from current iPhone to new iPhone wirelessly through WiFi, or wired through a cable. Depending on your iPhone models, you may need to use a USB-C to USB-C cable, Lightning to USB-C cable, or Lightning to Adaptor to Lightning set-up.

If possible, I would recommend a wired connection for data migration. Even the slow Lightning to USB-C cable can do 480Mbps. Although your WiFi may boast a faster speed, in practice it is often slower due to interference with your neighbor’s WiFi and room wall attenuation, and may also be less reliable.

Posted in Life, Smart Phone | Tagged: , , , , , | Leave a Comment »

Apple SIMD Vector and Matrix

Posted by binglongx on February 5, 2025

Include

Include for both C and C++ users:

#include <simd/simd.h>

C Users

Vector Types

C vector type example (see <simd/vector_types.h>):

simd_float3     // 3x1 column vector of float elements

If you look further, the vector is a Clang/GCC extension for SIMD architecture like AVX/Neon/OpenCL:

/*! @abstract A vector of three 32-bit floating-point numbers.
 *  @description In C++ and Metal, this type is also available as
 *  simd::float3. Note that vectors of this type are padded to have the same
 *  size and alignment as simd_float4.                                        */
typedef __attribute__((__ext_vector_type__(3))) float simd_float3;

You can regard it as an array of >= N elements that would fit into a SIMD wide register. 

The compiler has built-in support for:

  • Basic arithmetic operators for lanewise operations (vector-vector, and vector-scalar);
  • [i] to access i-th element;
  • .x.y.z.w , .xy etc. to access the elements.

Matrix Types

C matrix type example (see <simd/types.h>):

simd_float3x3  // 3x3 matrix of float elements

If you look further, the matrix is simply implemented as an array of columns:

/*! @abstract A matrix with 3 rows and 3 columns.                             */
typedef struct { simd_float3 columns[3]; } simd_float3x3;

Storage wise, the matrix is column major. Conceptually you use it as matrix without needs to care the storage format.

This also means you can access the column vectors easily, like

simd_float3x3 m;
simd_float3 column0 = m.columns[0];
simd_float3& column1 = m.columns[1];

There is no easy way to access a row vector or sub-matrix.

Vector Construction

Examples:

simd_double3 d3{1.0, 2.3, 4.5};                 // direct initialization
simd_float3 f3 = simd_make_float3(1, 2, 3.14f); // helper function
simd_float4 f4 = simd_make_float4(f3, 1);       // helper function

Matrix Construction

Direct initialization in column major:

simd_double3x3 d3x3{{
    {1, 0, 0}, // column 0
    {0,-1, 0}, // column 1
    {0, 0,-1}, // column 2
}};

Initialization with column vectors:

simd_float3x3 f3x3{
    simd_float3{1, 2, 3}, // column 0
    simd_float3{4, 5, 6}, // column 1
    simd_float3{7, 8, 9}, // column 2
};

Or as convenience, initialization with vectors for rows through a helper function:

simd_float3x3 f = simd_matrix_from_rows(
    simd_float3{1, 2, 3}, // row 0
    simd_float3{4, 5, 6}, // row 1
    simd_float3{7, 8, 9}  // row 2
);

Another example to construct a 4×4 transform matrix from 3×3 rotation matrix and 3×1 vector:

simd_float3x3 R;
simd_float3 t{1, 2, 3};
simd_float4x4 T{
    simd_make_float4(R.columns[0], 0), // column 0
    simd_make_float4(R.columns[1], 0), // column 1
    simd_make_float4(R.columns[2], 0), // column 2
    simd_make_float4(t, 1),            // column 3
};

Matrix Operations

Matrix operations can be found in <simd/matrix.h>, for example:

simd_float3 v1{1, 2, 3};
simd_float3x3 m1;
simd_float3 v2 = simd_mul(m1, v1);   // matrix * vector
simd_float3x3 m2;
simd_float3x3 m3 = simd_mul(m1, m2); // matrix * matrix

C++ Users

Vector Types

C++ vector type example (see <simd/vector_types.h>):

simd::float3     // 3x1 column vector of float elements

If you look further, it is just a synonym of the C type:

namespace simd {
    /*! @abstract A vector of three 32-bit floating-point numbers.
     *  @description In C or Objective-C, this type is available as
     *  simd_float3. Vectors of this type are padded to have the same size and
     *  alignment as simd_float4.                                               */
    typedef ::simd_float3 float3;
}

So the compiler has the same built-in support for:

  • Basic arithmetic operators for lanewise operations (vector-vector, and vector-scalar);
  • [i] to access i-th element;
  • .x.y.z.w , .xy etc. to access the elements.

Matrix Types

C++ matrix type example (see <simd/matrix_types.h>):

simd::float3x3  // 3x3 matrix of float elements

If you look further, the matrix type inherits the C matrix type with a few constructors added (but nothing else):

// in namespace simd
struct float3x3 : ::simd_float3x3 {
    float3x3() : ::simd_float3x3((simd_float3x3){0}) { }
    float3x3(float diagonal) : float3x3((float3)diagonal) { }
    float3x3(float3 v) : ::simd_float3x3((simd_float3x3){(float3){v.x,0,0}, (float3){0,v.y,0}, (float3){0,0,v.z}}) { }
    float3x3(float3 c0, float3 c1, float3 c2) : ::simd_float3x3((simd_float3x3){c0, c1, c2}) { }
    float3x3(::simd_float3x3 m) : ::simd_float3x3(m) { }
    float3x3(::simd_quatf q) : ::simd_float3x3(::simd_matrix3x3(q)) { }
};

Compared to the C matrix type, the constructors allow initializing the matrix more creatively: filling 0s, creating diagonal matrix, creating from columns, creating from C matrix, etc.

Because it is a thin wrapper over the C matrix, there is still no easy way to access a row vector or sub-matrix.

Vector Construction

Because the C++ vector is basically the same thing as the C vector type, you can use all the C means to initialize the object. There are also C++ helper functions to make vector objects, if you prefer.

simd::float3 f1{1.0, 2.3, 4.5};                   // direct initialization
simd::float3 f2 = simd_make_float3(1, 2, 3.14f);  // C helper function
simd::float4 f3 = simd_make_float4(f2, 1);        // C helper function
simd::float3 f4 = simd::make_float3(1, 2, 3.14f); // C++ helper function
simd::float4 f5 = simd::make_float4(f2, 1);       // C++ helper function

Matrix Construction

Because matrix is a class, you need to call one of the constructors to create a matrix object. For example, initialize through an intermediate C matrix using direct numbers:

simd::double3x3 d3x3{ simd_double3x3 {{
    {1, 0, 0}, // column 0
    {0,-1, 0}, // column 1
    {0, 0,-1}, // column 2
}} };

Initialization with column vectors:

simd::float3x3 f3x3{
    simd_float3{1, 2, 3},       // column 0: from C float3
    simd::float3{4, 5, 6},      // column 1: from C++ float3
    simd::make_float3(7, 8, 9), // column 2: from C++ helper function
};

If you need to construct from row vectors, call the same C helper function:

simd::float3x3 f3x3 = simd_matrix_from_rows(
    simd::float3{1, 2, 3}, // row 0
    simd::float3{4, 5, 6}, // row 1
    simd::float3{7, 8, 9}  // row 2
);

Matrix Operations

With operator overloading, it’s more pleasant to perform matrix operations in C++. Matrix operations can be found in <simd/matrix.h>, for example:

simd::float3 v1{1, 2, 3};
simd::float3x3 m1;
simd::float3 v2 = m1 * v1;      // matrix * vector
simd::float3x3 m2;
simd::float3x3 m3 = m1 * m2;    // matrix * matrix
simd::float3 v3 = m1 * m2 * v2; // matrix * matrix * vector

Conclusion

Apple SIMD library provides fast and simple vector and matrix operations.

Posted in C++ | Tagged: , , , , , , , , , , , | Leave a Comment »

24 Puzzle (Game to Get 24 out of 4 Integers)

Posted by binglongx on February 1, 2025

This a quick cheat if some friends challenge you the 24 puzzle: Run in Compiler explorer: https://godbolt.org/z/6aajvcrx5

The C++ code is certainly not optimized, but written cursorily:

#include <memory>           // std::unique_ptr
#include <optional>         // std::optional
#include <utility>          // std::move
#include <vector>           // std::vector
#include <variant>          // std::variant
#include <cassert>          // assert
#include <iostream>


enum class Operator {
    Add,
    Subtract,
    Multiply,
    Divide
};

struct Expression;

inline void printIndent(std::ostream& os, int indent) {
    for(int i=0; i<indent; ++i) {
        os << "  ";
    }
}

std::ostream& operator<<(std::ostream& os, Operator op) {
    switch(op){
        case Operator::Add:         os << "+"; break;
        case Operator::Subtract:    os << "-"; break;
        case Operator::Multiply:    os << "*"; break;
        case Operator::Divide:      os << "/"; break;
        default:                    assert(false); break;
    }
    return os;
}

struct BinaryExpression {
    std::unique_ptr<Expression> left;
    Operator                    op;
    std::unique_ptr<Expression> right;
    
    BinaryExpression(BinaryExpression&&) = default;
    BinaryExpression(std::unique_ptr<Expression> left, Operator op, std::unique_ptr<Expression> right);
    BinaryExpression clone() const;
    std::optional<int> evaluate() const;
    friend std::ostream& operator<< (std::ostream& os, const BinaryExpression& v);
};

struct Expression {
    std::variant<int, BinaryExpression> expr;   // terminal or binary expression
    
    Expression(BinaryExpression binaryExpr) : expr(std::move(binaryExpr)) {}
    Expression(int terminal) : expr(terminal) {}
    
    std::unique_ptr<Expression> clone() const {
        if( std::holds_alternative<int>(expr) ) {
            return std::make_unique<Expression>(std::get<int>(expr));
        }
        else {
            return std::make_unique<Expression>(std::get<BinaryExpression>(expr).clone());
        }
    }
    
    std::optional<int> evaluate() const {
        return std::holds_alternative<int>(expr) ?
        std::optional{std::get<int>(expr)} : std::get<BinaryExpression>(expr).evaluate();
    }
    
    friend std::ostream& operator<< (std::ostream& os, const Expression& v) {
        return std::holds_alternative<int>(v.expr)? (os << std::get<int>(v.expr)) : (os << std::get<BinaryExpression>(v.expr) );
    }
};

BinaryExpression::BinaryExpression(std::unique_ptr<Expression> left, Operator op, std::unique_ptr<Expression> right)
: left(std::move(left)), op(op), right(std::move(right)) {
}

BinaryExpression BinaryExpression::clone() const {
    return BinaryExpression{ left->clone(), op, right->clone() };
}

std::optional<int> BinaryExpression::evaluate() const {
    auto a = left->evaluate();
    auto b = right->evaluate();
    if( !a || !b ) {
        return {};          // error
    }
    switch(op) {
        case Operator::Add:         return (*a) + (*b);
        case Operator::Subtract:    return (*a) - (*b);
        case Operator::Multiply:    return (*a) * (*b);
        case Operator::Divide: {
            if( (*b) == 0 ) {
                return {};  // divided by 0
            }
            else if( (*a) % (*b) != 0 ) {
                return {};  // has remainder
            }
            else {
                return (*a) / (*b); // good
            }
        }
        default:
            assert(false);  // should not be here.
            return {};
    }
}

std::ostream& operator<< (std::ostream& os, const BinaryExpression& v) {
    return os << "(" << *v.left << v.op << *v.right << ")";
}


std::optional<std::unique_ptr<Expression>> get_expression_for_target(const std::vector<std::unique_ptr<Expression>>& expressions, int target);

// add `ab` to end of `others` and try to shoot target
// if failure, return empty, and restore `others` (for next try later)
// if success, return the valid expression that evaluates to `target`
std::optional<std::unique_ptr<Expression>> get_expression_for_target(std::unique_ptr<Expression> ab, std::vector<std::unique_ptr<Expression>>& others, int target) {
    others.push_back( std::move(ab) );
    if(auto result = get_expression_for_target(others, target)) {
        return result;
    }
    // did not work: revert `others`.
    others.pop_back();
    return {};
}

// try to construct an expression using members in `expressions` exactly once with operators (+,-,*,/) to evaluate to `target`
// if failure, return empty.
// if success, return the valid expression that evaluates to `target`
std::optional<std::unique_ptr<Expression>> get_expression_for_target(const std::vector<std::unique_ptr<Expression>>& expressions, int target) {
    if( expressions.size()==0u ) {
        return {};  // no way
    }
    
    // base case
    if( expressions.size()==1u ) {
        if( auto value = expressions.front()->evaluate(); value && *value == target ) {
            return expressions.front()->clone();
        }
        else {
            return {};  // no result
        }
    }
    
    // reduce to a size-1 problem by combining 2 arbitrary expressions
    for(size_t i=0; i<expressions.size()-1u; ++i) {
        for(size_t j=i+1; j<expressions.size(); ++j) {
            auto& a = expressions[i];
            auto& b = expressions[j];
            
            std::vector<std::unique_ptr<Expression>> others;
            for(size_t k=0; k<expressions.size(); ++k) {
                if( k!=i && k!=j) {
                    others.push_back(expressions[k]->clone());
                }
            }
            
            // a + b
            if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(a->clone(), Operator::Add, b->clone())),
                                                       others, target)) {
                return result;
            }
            
            // a - b
            if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(a->clone(), Operator::Subtract, b->clone())),
                                                       others, target)) {
                return result;
            }
            
            // b - a
            if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(b->clone(), Operator::Subtract, a->clone())),
                                                       others, target)) {
                return result;
            }
            
            // a * b
            if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(a->clone(), Operator::Multiply, b->clone())),
                                                       others, target)) {
                return result;
            }
            
            // a / b
            if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(a->clone(), Operator::Divide, b->clone())),
                                                       others, target)) {
                return result;
            }
            
            // b / a
            if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(b->clone(), Operator::Divide, a->clone())),
                                                       others, target)) {
                return result;
            }
        }
    }
    return {};  // no result
}

std::vector<std::unique_ptr<Expression>> create_expressions(const std::vector<int>& numbers) {
    std::vector<std::unique_ptr<Expression>> expressions;
    for(auto number : numbers) {
        expressions.push_back(std::make_unique<Expression>(number));
    }
    return expressions;
}

void test(int target, const std::vector<int>& numbers) {
    
    std::cout << "Trying to get " << target << " from: ";
    for(auto number : numbers) {
        std::cout << number << " ";
    }
    
    if( auto expr = get_expression_for_target(create_expressions(numbers), target) ) {
        std::cout << "  Success: " << (**expr) << "\n";
    }
    else {
        std::cout << "  Failure: No result\n";
    }
}


int main() {
    test(24, std::vector<int>{1,1,1,1,1});
    test(24, std::vector<int>{2,2,2,2,2});
    test(24, std::vector<int>{3,3,3,3,3});
    test(24, std::vector<int>{4,4,4,4,4});
    test(24, std::vector<int>{5,5,5,5,5});
    test(24, std::vector<int>{6,6,6,6,6});
    test(24, std::vector<int>{7,7,7,7,7});
    test(24, std::vector<int>{8,8,8,8,8});
    test(24, std::vector<int>{9,9,9,9,9});
    return 0;
}

Note that it can handle any length of numbers, not necessorily 4 numbers. The target does not have to be 24 either. Don’t use a lot of numbers; it might be slow as it is doing exhsautive searching.

The testing results above:

Trying to get 24 from: 1 1 1 1 1   Failure: No result
Trying to get 24 from: 2 2 2 2 2   Success: ((2+2)*(2+(2+2)))
Trying to get 24 from: 3 3 3 3 3   Success: ((3+3)+(3*(3+3)))
Trying to get 24 from: 4 4 4 4 4   Success: ((4*(4+4))-(4+4))
Trying to get 24 from: 5 5 5 5 5   Success: (((5*(5*5))-5)/5)
Trying to get 24 from: 6 6 6 6 6   Success: ((6+6)*((6+6)/6))
Trying to get 24 from: 7 7 7 7 7   Failure: No result
Trying to get 24 from: 8 8 8 8 8   Success: ((8+8)-(8-(8+8)))
Trying to get 24 from: 9 9 9 9 9   Failure: No result

Posted in C++ | Tagged: , , , , | Leave a Comment »