n****e
发帖数: 678 | 1 void memmov(void* src, void* dst, int numBytes) {
}
两位国人大哥一起面，自己对void pointer的概念有点忘了，这题也做得不好。
多谢国人大哥高抬贵手，让我过了。
bless一下自己后面的on-site。 |
g*********e
发帖数: 14401 | |
n****e
发帖数: 678 | 3 店面就一题，国人大哥主要是以technical discussion为主。。。
【在 g*********e 的大作中提到】
: 就一题吗？
|
s********u
发帖数: 1109 | 4 这个是说他会给什么api么。。还是说要求thread-safe之类 |
n****e
发帖数: 678 | 5 就是implement memmov 这个function。
有做alignment之类的优化。
没有要求thread-safe。
【在 s********u 的大作中提到】
: 这个是说他会给什么api么。。还是说要求thread-safe之类
|
f**********3
发帖数: 295 | 6 要不要handle src+numBytes > dst的情况？
【在 n****e 的大作中提到】
: void memmov(void* src, void* dst, int numBytes) {
: }
: 两位国人大哥一起面，自己对void pointer的概念有点忘了，这题也做得不好。
: 多谢国人大哥高抬贵手，让我过了。
: bless一下自己后面的on-site。
|
s********u
发帖数: 1109 | 7 哦我懂了，就是类似copy string对吧。alignment的话需要考虑原来有没有数据吧？
【在 n****e 的大作中提到】
: 就是implement memmov 这个function。
: 有做alignment之类的优化。
: 没有要求thread-safe。
|
n****e
发帖数: 678 | 8 需要。
还有 dst + numBytes > src
【在 f**********3 的大作中提到】
: 要不要handle src+numBytes > dst的情况？
|
d**********x
发帖数: 4083 | 9 btw, one possible optimization is to move as much as possible (4 bytes or 8
bytes) each time, instead of one byte
【在 n****e 的大作中提到】
: 就是implement memmov 这个function。
: 有做alignment之类的优化。
: 没有要求thread-safe。
|
n****e
发帖数: 678 | 10 alignment是从performance的角度来考虑。 主要是对 src 的address来做。
这个我也不清楚有没有做对。 国人大哥的考虑是说，cpu每次读32bit的数，也就是4
bytes，所以要让pointer address 对齐 4 bytes （这个是我的理解）。 可是，我觉
得这个是cpu 自身就会handle的事情。
当时 我写的是：newSrc = ((char*)src >> 2) << 2; 然后，再对dst address进行相
应的调整。
【在 s********u 的大作中提到】
: 哦我懂了，就是类似copy string对吧。alignment的话需要考虑原来有没有数据吧？
|
|
|
d**********x
发帖数: 4083 | 11 you are right.
memmove handles this, while memcopy and strcpy don't.
【在 n****e 的大作中提到】
: 需要。
: 还有 dst + numBytes > src
|
n****e
发帖数: 678 | 12 这个有说，问题是总共移动的bytes还是一样的。 能说说为什么移动4 bytes可以
improve performance？
8
【在 d**********x 的大作中提到】
: btw, one possible optimization is to move as much as possible (4 bytes or 8
: bytes) each time, instead of one byte
|
n****e
发帖数: 678 | 13 为什么memcopy 和 strcpy 不需要呢？
【在 d**********x 的大作中提到】
: you are right.
: memmove handles this, while memcopy and strcpy don't.
|
d**********x
发帖数: 4083 | 14 as you said, 32bits cpu read 4 bytes each time...
when you read one byte in c, cpu still read 4 bytes...
next time you read one byte, cpu will go to cache and read these 4 bytes
again...
similar for write
or
【在 n****e 的大作中提到】
: 这个有说，问题是总共移动的bytes还是一样的。 能说说为什么移动4 bytes可以
: improve performance？
:
: 8
|
d**********x
发帖数: 4083 | 15 don't know the reasoning. but that's what i learned from reading glibc...
【在 n****e 的大作中提到】
: 为什么memcopy 和 strcpy 不需要呢？
|
n****e
发帖数: 678 | 16 哦，知道了，这下make sense了。 所以是在做完alignment之后，用（float *）src
在 进行+1 对吧
【在 d**********x 的大作中提到】
: as you said, 32bits cpu read 4 bytes each time...
: when you read one byte in c, cpu still read 4 bytes...
: next time you read one byte, cpu will go to cache and read these 4 bytes
: again...
: similar for write
:
: or
|
n****e
发帖数: 678 | 17 我都没有读过glibc。。。
【在 d**********x 的大作中提到】
: don't know the reasoning. but that's what i learned from reading glibc...
|
w*******e
发帖数: 395 | 18 如果，src和dest有不同的aligment怎么办呢？
比如src移了2个byte后就是4-byte aligned，但是dest本身就是4-byte aligned，不需
要移动，那你优化了src，但是dest写的时候又不是aligned。
这总情况怎么办？
【在 n****e 的大作中提到】
: 哦，知道了，这下make sense了。 所以是在做完alignment之后，用（float *）src
: 在 进行+1 对吧
|
n****e
发帖数: 678 | 19 这里对读进行了优化，确实没法同时align src 和 dst
【在 w*******e 的大作中提到】
: 如果，src和dest有不同的aligment怎么办呢？
: 比如src移了2个byte后就是4-byte aligned，但是dest本身就是4-byte aligned，不需
: 要移动，那你优化了src，但是dest写的时候又不是aligned。
: 这总情况怎么办？
|
s**x
发帖数: 7506 | 20
多读一个 word, 然后再 merge 一下吧。
曾被问到一个类似的题，you can not read single bytes, you can only read/write
a whole word from certain alignment, 直接晕倒。
【在 n****e 的大作中提到】
: 这里对读进行了优化，确实没法同时align src 和 dst
|
|
|
V*********r
发帖数: 666 | 21 从学习的角度（比如标准库里各种函数的实现），看tcc里标准库的实现会不会比看
glibc更省事一些？
【在 d**********x 的大作中提到】
: don't know the reasoning. but that's what i learned from reading glibc...
|
d**********x
发帖数: 4083 | 22 not sure...
at least glibc is not good for read. they even had some outdated and
misleading comments in their code...
【在 V*********r 的大作中提到】
: 从学习的角度（比如标准库里各种函数的实现），看tcc里标准库的实现会不会比看
: glibc更省事一些？
|
J****3
发帖数: 427 | |
s**x
发帖数: 7506 | 24 http://stuff.mit.edu/afs/sipb/contrib/linux/arch/microblaze/lib
/*
* Copyright (C) 2008-2009 Michal Simek
* Copyright (C) 2008-2009 PetaLogix
* Copyright (C) 2007 John Williams
*
* Reasonably optimised generic C-code for memcpy on Microblaze
* This is generic C code to do efficient, alignment-aware memmove.
*
* It is based on demo code originally Copyright 2001 by Intel Corp, taken
from
* http://www.embedded.com/showArticle.jhtml?articleID=19205567
*
* Attempts were made, unsuccessfully, to contact the original
* author of this code (Michael Morrow, Intel). Below is the original
* copyright notice.
*
* This software has been developed by Intel Corporation.
* Intel specifically disclaims all warranties, express or
* implied, and all liability, including consequential and
* other indirect damages, for the use of this program, including
* liability for infringement of any proprietary rights,
* and including the warranties of merchantability and fitness
* for a particular purpose. Intel does not assume any
* responsibility for and errors which may appear in this program
* not any responsibility to update it.
*/
#include
#include
#include
#include
#include
#ifdef __HAVE_ARCH_MEMMOVE
#ifndef CONFIG_OPT_LIB_FUNCTION
void *memmove(void *v_dst, const void *v_src, __kernel_size_t c)
{
const char *src = v_src;
char *dst = v_dst;
if (!c)
return v_dst;
/* Use memcpy when source is higher than dest */
if (v_dst <= v_src)
return memcpy(v_dst, v_src, c);
/* copy backwards, from end to beginning */
src += c;
dst += c;
/* Simple, byte oriented memmove. */
while (c--)
*--dst = *--src;
return v_dst;
}
#else /* CONFIG_OPT_LIB_FUNCTION */
void *memmove(void *v_dst, const void *v_src, __kernel_size_t c)
{
const char *src = v_src;
char *dst = v_dst;
const uint32_t *i_src;
uint32_t *i_dst;
if (!c)
return v_dst;
/* Use memcpy when source is higher than dest */
if (v_dst <= v_src)
return memcpy(v_dst, v_src, c);
/* The following code tries to optimize the copy by using unsigned
* alignment. This will work fine if both source and destination are
* aligned on the same boundary. However, if they are aligned on
* different boundaries shifts will be necessary. This might result in
* bad performance on MicroBlaze systems without a barrel shifter.
*/
/* FIXME this part needs more test */
/* Do a descending copy - this is a bit trickier! */
dst += c;
src += c;
if (c >= 4) {
unsigned value, buf_hold;
/* Align the destination to a word boundary. */
/* This is done in an endian independent manner. */
switch ((unsigned long)dst & 3) {
case 3:
*--dst = *--src;
--c;
case 2:
*--dst = *--src;
--c;
case 1:
*--dst = *--src;
--c;
}
i_dst = (void *)dst;
/* Choose a copy scheme based on the source */
/* alignment relative to dstination. */
switch ((unsigned long)src & 3) {
case 0x0: /* Both byte offsets are aligned */
i_src = (const void *)src;
for (; c >= 4; c -= 4)
*--i_dst = *--i_src;
src = (const void *)i_src;
break;
case 0x1: /* Unaligned - Off by 1 */
/* Word align the source */
i_src = (const void *) (((unsigned)src + 4) & ~3);
#ifndef __MICROBLAZEEL__
/* Load the holding buffer */
buf_hold = *--i_src >> 24;
for (; c >= 4; c -= 4) {
value = *--i_src;
*--i_dst = buf_hold << 8 | value;
buf_hold = value >> 24;
}
#else
/* Load the holding buffer */
buf_hold = (*--i_src & 0xFF) << 24;
for (; c >= 4; c -= 4) {
value = *--i_src;
*--i_dst = buf_hold |
((value & 0xFFFFFF00) >> 8);
buf_hold = (value & 0xFF) << 24;
}
#endif
/* Realign the source */
src = (const void *)i_src;
src += 1;
break;
case 0x2: /* Unaligned - Off by 2 */
/* Word align the source */
i_src = (const void *) (((unsigned)src + 4) & ~3);
#ifndef __MICROBLAZEEL__
/* Load the holding buffer */
buf_hold = *--i_src >> 16;
for (; c >= 4; c -= 4) {
value = *--i_src;
*--i_dst = buf_hold << 16 | value;
buf_hold = value >> 16;
}
#else
/* Load the holding buffer */
buf_hold = (*--i_src & 0xFFFF) << 16;
for (; c >= 4; c -= 4) {
value = *--i_src;
*--i_dst = buf_hold |
((value & 0xFFFF0000) >> 16);
buf_hold = (value & 0xFFFF) << 16;
}
#endif
/* Realign the source */
src = (const void *)i_src;
src += 2;
break;
case 0x3: /* Unaligned - Off by 3 */
/* Word align the source */
i_src = (const void *) (((unsigned)src + 4) & ~3);
#ifndef __MICROBLAZEEL__
/* Load the holding buffer */
buf_hold = *--i_src >> 8;
for (; c >= 4; c -= 4) {
value = *--i_src;
*--i_dst = buf_hold << 24 | value;
buf_hold = value >> 8;
}
#else
/* Load the holding buffer */
buf_hold = (*--i_src & 0xFFFFFF) << 8;
for (; c >= 4; c -= 4) {
value = *--i_src;
*--i_dst = buf_hold |
((value & 0xFF000000) >> 24);
buf_hold = (value & 0xFFFFFF) << 8;
}
#endif
/* Realign the source */
src = (const void *)i_src;
src += 3;
break;
}
dst = (void *)i_dst;
}
/* simple fast copy, ... unless a cache boundary is crossed */
/* Finish off any remaining bytes */
switch (c) {
case 4:
*--dst = *--src;
case 3:
*--dst = *--src;
case 2:
*--dst = *--src;
case 1:
*--dst = *--src;
}
return v_dst;
}
#endif /* CONFIG_OPT_LIB_FUNCTION */
EXPORT_SYMBOL(memmove);
#endif /* __HAVE_ARCH_MEMMOVE */ |
J****3
发帖数: 427 | 25 不知道楼主面试的时候 如果在处理没有Overlap情况的时候可以直接call memcpy 么？
【在 s**x 的大作中提到】
: http://stuff.mit.edu/afs/sipb/contrib/linux/arch/microblaze/lib
: /*
: * Copyright (C) 2008-2009 Michal Simek
: * Copyright (C) 2008-2009 PetaLogix
: * Copyright (C) 2007 John Williams
: *
: * Reasonably optimised generic C-code for memcpy on Microblaze
: * This is generic C code to do efficient, alignment-aware memmove.
: *
: * It is based on demo code originally Copyright 2001 by Intel Corp, taken
|
s**x
发帖数: 7506 | 26 当然不能，memcpy 估计就 5 行 程序阿。
【在 J****3 的大作中提到】
: 不知道楼主面试的时候 如果在处理没有Overlap情况的时候可以直接call memcpy 么？
|
J****3
发帖数: 427 | 27 不会就5行吧？难道就一个loop 一个个byte 的copy吗？
【在 s**x 的大作中提到】
: 当然不能，memcpy 估计就 5 行 程序阿。
|
s**x
发帖数: 7506 | 28 void *memmove(void *src, void *dst, size_t n)
{
if (n == 0 || src == dst) return;
char *cs = src;
char *cd = dst;
if (cd < cs) {
while (n--) {
*cd = *cs;
cd ++;
cs ++;
}
} else {
cd += n;
cs += n;
while (n--) {
*cd = *cs;
cd --;
cs --;
}
}
return dst;
}
【在 J****3 的大作中提到】
: 不会就5行吧？难道就一个loop 一个个byte 的copy吗？
|
n****e
发帖数: 678 | 29 没有用memcpy啊
【在 J****3 的大作中提到】
: 不知道楼主面试的时候 如果在处理没有Overlap情况的时候可以直接call memcpy 么？
|
V*********r
发帖数: 666 | 30 能否推荐一个适合阅读或教学的C标准库的实现？最好是全C，不带汇编的。
【在 s**x 的大作中提到】
: http://stuff.mit.edu/afs/sipb/contrib/linux/arch/microblaze/lib
: /*
: * Copyright (C) 2008-2009 Michal Simek
: * Copyright (C) 2008-2009 PetaLogix
: * Copyright (C) 2007 John Williams
: *
: * Reasonably optimised generic C-code for memcpy on Microblaze
: * This is generic C code to do efficient, alignment-aware memmove.
: *
: * It is based on demo code originally Copyright 2001 by Intel Corp, taken
|
|
|
V*********r
发帖数: 666 | 31 glibc早期的版本比如1.09会不会简单一些...
【在 d**********x 的大作中提到】
: not sure...
: at least glibc is not good for read. they even had some outdated and
: misleading comments in their code...
|
