---
# System prepended metadata

title: String and Sorting
tags: [EMBEDDED_C]

---

# String and Sorting
###### tags: `EMBEDDED_C`




- [x] String and Pointer
- [x] String Copy
- [x] String Length
- [ ] <font style="color:red"> **String Reverse** </font>
- [ ] isPalidome
- [ ] StrStr
- [ ] Strdup vs strcpy
- [ ] 以一個單字為單位 反轉一個輸入字串(不是每個字元反轉過來)
- [ ] 給定一個prefix(第一行輸入)，輸出不包含此prefix的string
- [ ] Quick Sort
- [ ] Binary Search
- [ ] Bubble Sort

## 待整理題目
#### 2. 以一個單字為單位 反轉一個輸入字串(不是每個字元反轉過來)
(如:I am a boy 變成 boy a am I)
#### 給定一個prefix(第一行輸入)，輸出不包含此prefix的string

input:
```
aaaa
aaaabbbbccc
badssssd
mdjeld
bbaaaakkdkd
```
output:
```
badssssd
mdjeld
bbaaaakkdkd
```


## String abd Pointer 
```clike=
int myStrLength(const char *p_mystr) {
int count = 0;
    while( *p_mystr != '\0'){                                    
        count ++;                                   
        p_mystr++;
    }
    return count;                                            
}                                        
int main(void){                                    
    char *test = "Suck My Dick";                        
    char strArry[36] = "Suck My Dick!";        
    printf("The length of string: %s is %d\n",\ 
            &strArry[0], myStrLength(strArry));
    return 0;
} 
```


## String Copy
寫出一個字串拷貝程式： 
void StrCpy(char* dst , char* src) ;
* 如果想要優化？ ??? **NEON** ???
```cpp=
// array version
void strcpy(char *dst, char *src){  
    int i = 0;
    while((src[i] = dst[i]) != '\0')
    i++;
}
// pointer version
void strcpy(const char *s, char *t)  
   while((*s = *t) != '\0') {
       s++;
       t++;
   }
}
```
## String Length 
Implement the funcytion `int strlen( const char *str )`

```cpp=
int strlen( const char *str ){
     int len;
     while( (*str++) != '\0' ){
         len++;
     }
     
     //while((*str++))
    
     return len;
}
```
* My version
```cpp=
int str_len(const char* str){
    int len;

    while(*str != '\0'){
        len++;
        str++;
    }
    return len;
}
```

## Swap implementation comparsion
  - Environment: Macbook Air M1
    - Command: clang -g -O3 -c ./swap_compare.c -o a.out && /opt/homebrew/opt/binutils/bin/gobjdump -dSl ./a.out | less
  - Integer
    - Use temp 
        - C code
       ```c=
        void swap(int * a, int * b)
        {                          
            int tmp = *a;      
            *a = *b;           
            *b = tmp;          
        }      
        ```
        - Dissaembly
        ```asm=
        swap_int():
        ./swap_compare.c:4

        void swap_int(int * a, int * b)
        {
            int tmp = *a;
           0:   b9400008        ldr     w8, [x0]
        ./swap_compare.c:5
            *a = *b;
           4:   b9400029        ldr     w9, [x1]
           8:   b9000009        str     w9, [x0]
        ./swap_compare.c:6                      
            *b = tmp;                           
           c:   b9000028        str     w8, [x1]
        ./swap_compare.c:7                      
        }                                       
          10:   d65f03c0        ret             
        ```
    - Use XOR
        - C code
        ```c=
        void swap_int_xor(int *a, int  *b) 
        {                                 
            *a ^= *b;                     
            *b ^= *a;                     
            *a ^= *b;                     
        }      
        ```
        - Disassembly
        ```asm=
        0000000000000014 <_swap_int_xor>:         
        swap_int_xor():                           
        ./swap_compare.c:11                       

        void swap_int_xor(int *a, int  *b)        
        {                                         
            *a ^= *b;                             
          14:   b9400028        ldr     w8, [x1]  
          18:   b9400009        ldr     w9, [x0]  
          1c:   4a080128        eor     w8, w9, w8
          20:   b9000008        str     w8, [x0]  
        ./swap_compare.c:12                       
            *b ^= *a;                             
          24:   b9400029        ldr     w9, [x1]  
          28:   4a080128        eor     w8, w9, w8
          2c:   b9000028        str     w8, [x1]  
        ./swap_compare.c:13                       
            *a ^= *b;                             
          30:   b9400009        ldr     w9, [x0]  
          34:   4a080128        eor     w8, w9, w8
          38:   b9000008        str     w8, [x0]  
        ./swap_compare.c:14                       
        }                                         
          3c:   d65f03c0        ret               
        ```
  - char
    - Use temp 
        - C code
        ```c=
        void swap(char **a, char **b)
        {
            char ** tmp = *a;
            **a = **b;
            **b = **tmp;
        }
        ```
        - Disassembly
        ```asm=
        0000000000000014 <_swap_int_xor>:         
        swap_int_xor():                           
        ./swap_compare.c:11                       

        void swap_int_xor(int *a, int  *b)        
        {                                         
            *a ^= *b;                             
          14:   b9400028        ldr     w8, [x1]  
          18:   b9400009        ldr     w9, [x0]  
          1c:   4a080128        eor     w8, w9, w8
          20:   b9000008        str     w8, [x0]  
        ./swap_compare.c:12                       
            *b ^= *a;                             
          24:   b9400029        ldr     w9, [x1]  
          28:   4a080128        eor     w8, w9, w8
          2c:   b9000028        str     w8, [x1]  
        ./swap_compare.c:13                       
            *a ^= *b;                             
          30:   b9400009        ldr     w9, [x0]  
          34:   4a080128        eor     w8, w9, w8
          38:   b9000008        str     w8, [x0]  
            ./swap_compare.c:14                       
            }                                         
          3c:   d65f03c0        ret               
        ```
    - Use XOR
        - C code
        ```c=
        void swap_char_xor(char **a, char **b)
        {
            **a ^= **b;
            **b ^= **a;
            **a ^= **b;
        }
        ```
        - Disassembly
        ```asm=
        0000000000000060 <_swap_char_xor>:         
        swap_char_xor():                           
        ./swap_compare.c:25                        

        void swap_char_xor(char **a, char **b)     
        {                                          
            **a ^= **b;                            
          60:   f9400028        ldr     x8, [x1]   
          64:   39400108        ldrb    w8, [x8]   
          68:   f9400009        ldr     x9, [x0]   
          6c:   3940012a        ldrb    w10, [x9]  
          70:   4a080148        eor     w8, w10, w8
          74:   39000128        strb    w8, [x9]   
        ./swap_compare.c:26                        
            **b ^= **a;                            
          78:   f9400008        ldr     x8, [x0]   
          7c:   39400108        ldrb    w8, [x8]   
          80:   f9400029        ldr     x9, [x1]   
          84:   3940012a        ldrb    w10, [x9]  
          88:   4a080148        eor     w8, w10, w8
          8c:   39000128        strb    w8, [x9]   
        ./swap_compare.c:27                        
            **a ^= **b;                            
          90:   f9400028        ldr     x8, [x1]   
          94:   39400108        ldrb    w8, [x8]   
          98:   f9400009        ldr     x9, [x0]   
          9c:   3940012a        ldrb    w10, [x9]  
          a0:   4a080148        eor     w8, w10, w8
          a4:   39000128        strb    w8, [x9]   
        ./swap_compare.c:28                        
        }                                          
          a8:   d65f03c0        ret                
        ```
    
## isPalidome
## Reverse String

```cpp=

void reverseString(char *p_str){
    char *str_end = pstr +　str_len(p_str) -1;
    char tmp      = 0;
    
    while(str_end >> p_str){
        tmp = str;
    }
}
```
* 巧虎
```cpp=
#include <stdio.h>
static void swap(char **a, char **b)
{
    **a ^= **b;
    **b ^= **a;
    **a ^= **b;
}

static void reverse(char *s)
{
    char *p = s;

    // this time, p point to \0 
    while(p && *++p != '\0'){}

    for(p--; s < p; p--, s++)
        swap(&p, &s);
}

int main(int argc, char **argv)
{
    if(argc < 2){
        printf("%s [string]\n", argv[0]);
        return -1;
    }

    printf("Before : %s\n", argv[1]);
    reverse(argv[1]);
    printf("After reverse: %s\n", argv[1]);

    return 0;
}

```
### c語言遞迴反向輸出標準字符串[AMD]
## `strcpy` vs `strdup`

## `strdup`

## `strstr`
```cpp=
if (NULL != strstr())
```


```cpp=
static void string_cpy(const char *src_p, char *dst_p){  
    while(*src_p != '\0'){ 
        *dst_p = *src_p;     
        src_p++;   
        dst_p++;  
    }    
}                                                                                                                                                                                       
                                                                                                                                                                                        
static int string_length(const char *strlen_p){ 
    int count = 0;
    
    while(*strlen_p != '\0'){   
        count++;
        strlen_p++; 
    }
}                                                                                                                                                   
static void string_reverse(char *reverse_p){ 

    int count = string_length(reverse_p) -1; 
    char *start_p = reverse_p;
    char *end_p   = reverse_p; 
    char ch_tmp; 
    
    end_p = reverse_p + count; 

    while(end_p > start_p){  
        ch_tmp     = *start_p;  
        *start_p = *end_p;  
        *end_p     = ch_tmp; 
        end_p++;       
        reverse_p++;
    }
}                                              
```
## Other
1. Waht'e the result?
```cpp=
char *ptr = "Supermicro USA"
*ptr ++;
printf("%s\n", ptr);
ptr++;
printf("%s\n", ptr);
```

## Review
```cpp=
int str_len(const char *src) {  
    int count = 0;    
    while(*src != '\0') {   
        src++;    
        count++;  
    }   
    return count;                   
}                                                                                                                                                                                                          
                                                                                                                                                                                                           
void str_cpy(const char *src, char *dst) { 
    while(*src != '\0') {   
        *dst = *src;  
        src++; 
        dst++;   
    } 
}                                                                          
bool isPalidome(const char *src) {  
    char *forward  = src;          
    char *backward = src;   
    int  len       = (str_len(src) - 1) /2;   
    forward  += len;                
    backward += len;    
    while(*forward != '\0') {  
        if(*forward != *backward) {      
            return false;     
        }  
        forward++; 
        backward--;   
    }
    return true;   
}  
int main(void) {  
    char a[32] = "Suck My Dick!"; 
    char c[32] = "ABCDCBA";               
    char d[32] = "ABCDDCBA";   
    printf("%s's length is %d\n", c, str_len(c)); 
    if( isPalidome(c) == true) 
        printf("%s is Palidome\n", c);  
    else 
        printf("%s is not Palidome\n", c);       
}
```

### 

```c=
void transform(int *ptr) {                                                                                                                                                                                 
                                                                                                                                                                                                           
        int arry[8] = {0};                                                                                                                                                                                 
                                                                                                                                                                                                           
        for(int i = 7; i >= 0; i--) {                                                                                                                                                                      
                arry[i] = (*ptr) % 10;                                                                                                                                                                     
                *ptr    = (*ptr) / 10;                                                                                                                                                                     
        }                                                                                                                                                                                                  
        *ptr = 0;                                                                                                                                                                                          
                                                                                                                                                                                                           
        for(int i = 0; i < 8; i++) {                                                                                                                                                                       
                printf("arry[%d]:%d\n", i, arry[i]);                                                                                                                                                       
        }                                                                                                                                                                                                  
        for(int i = 4; i < 8; i++) {                                                                                                                                                                       
                *ptr = (*ptr) * 10;                                                                                                                                                                        
                *ptr = *ptr   + arry[i];                                                                                                                                                                   
        }                                                                                                                                                                                                  
        for(int i = 0; i < 4; i++) {                                                                                                                                                                       
                *ptr = (*ptr) * 10;                                                                                                                                                                        
                *ptr = *ptr   + arry[i];                                                                                                                                                                   
        }                                                                                                                                                                                                  
}                                      

```
## Quick Sort
## Bubble Sort
## Binary Search

## Reference
* [[請益] 發哥上機考準備 DCARD](https://www.dcard.tw/f/tech_job/p/236515024)
* 